Ciao, sto provando a fare questo esercizio e il mio ragionamento mi sembra corretto, ho provato con alcuni test case presenti sulla piattaforma e non e funziona ma il punteggio è 0/100 perchè non restituisce un output corretto in alcuni casi. Cosa sto tralasciando?
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
long int N, M, T;
vector <long int> A, B, C, E, tmin;
vector <bool> visitato;
int main()
{
ifstream cin("input.txt");
ofstream cout("output.txt");
cin >> N >> M >> T;
A.resize(M);
B.resize(M);
C.resize(M);
E.resize(M);
tmin.resize(N);
visitato.resize(N);
tmin[0]=0;
for (int i=0; i<N; i++)
{
visitato[i]=false;
}
for (int i=0; i<M; i++)
cin >> A[i] >> B[i] >> C[i] >> E[i];
for (int i=0; i<N; i++)
{
for (int j=0; j<M; j++)
{
if (A[j]==i)
{
long int temp=C[j]+tmin[i];
if (visitato[B[j]]==true&&temp<tmin[B[j]])
{
tmin[B[j]]=temp;
}
else if (visitato[B[j]]==false&&(E[j]==0||temp<=T))
{
visitato[B[j]]=true;
tmin[B[j]]=temp;
}
}
}
}
if (visitato[N-1]==false)
tmin[N-1]=-1;
cout << tmin[N-1] << endl;
return 0;
}
Ciao, nella tua soluzione sono presenti diversi errori proprio a livello di logica più che di implementazione.
La prima cosa che salta all’occhio è come questa soluzione, anche ammesso produca la risposta corretta sia troppo lenta, infatti per ogni nodo stai iterando su tutti gli archi, il che ti porta ad una complessità di O(NM) che è troppo alta per questo problema. Inoltre puoi accorgerti che tutte queste iterazioni che fai sono inutili perché poi controlli se il primo estremo dell’arco è effettivamente il nodo corrente, finendo per iterare per ogni nodo su tutti i suoi archi uscenti in maniera molto inefficiente. Questo può essere sistemato molto velocemente passando dalla tua rappresentazione del grafo a lista di archi ad una lista di adiacenza (puoi trovare del materiale al riguardo sulla piattaforma algobadge).
Per quanto riguarda la logica che applichi quando stai controllando un arco, mi sembra abbastanza corretta tranne che per una cosa, ovvero che tu assumi che se il nodo B[j] era già stato raggiunto con tmin[B[j]] > temp allora sicuramente l’arco che sto guardando in questo momento lo posso percorrere, ciò però non è detto perché è possibile che il nodo fosse stato precedentemente raggiunto tramite una strada che non esplodeva e quindi è possibile che tmin[B[j]] superi effettivamente T, per cui non hai alcuna garanzia che la strada attuale non esploderà durante il transito. Questo può essere risolto semplicemente ogni volta controllando se l’arco esploderebbe o meno a prescindere dal fatto che B[j] sia già stato raggiunto o meno.
Il problema più grande però, è l’ordine in cui visiti gli archi, infatti tu stai guardando prima tutti gli archi uscenti dal nodo 0, poi dal nodo 1, e così via, ma visitarli in quest’ordine non è detto che dia la risposta corretta. Per esempio, prendi il seguente grafo:
0 → 2 → 1 → 3
Supponendo che tutti gli archi abbiano peso 1, e che nessuno esploda, la risposta corretta sarebbe 3, ma la tua soluzione stampa 1. Questo è dovuto a due motivi:
Come accennavo prima, l’ordine in cui consideri gli archi è sbagliato, infatti la tua soluzione andrà a considerare l’arco 1 → 3 prima di aver considerato l’arco 2 → 1, quindi nel momento in cui consideri l’arco 1 → 3, la risposta memorizzata nel nodo 1 è sbagliata portando ad una risposta sbagliata anche sul nodo 3. L’ordine in cui vorresti visitare gli archi è quello in cui in ogni momento tu visiti gli archi uscenti da un nodo che sicuramente ha già la risposta corretta, perché altrimenti se poi si rivelasse che la risposta per quel nodo era sbagliata anche tutte le altre che sono state calcolate di conseguenza saranno sbagliate dovendole poi ricalcolare. Questo ordinamento effettivamente esiste ed è quello dato dall’algoritmo di dijkstra (che puoi trovare sempre su algobadge), che in questo problema è applicabile perché C_i \ge 0, in particolare hai C_i \ge 1, ma anche la precedente sarebbe sufficiente.
Il secondo motivo è che la tua soluzione considera anche i nodi che non sono mai stati raggiunti, portandoti a considerare un nodo potenzialmente irraggiungibile come un nodo che può essere raggiunto in un tempo pari a 0. Questo è il motivo per cui la tua soluzione stampa 1 sull’esempio di prima, perché quando consideri l’arco 1 → 3, il nodo 1 non è stato mai raggiunto tramite l’arco 2 → 1 (che è l’unico modo per raggiungere il nodo 1), e quindi tu consideri corretto il valore tmin[1] quando in realtà questo valore è 0 perché il nodo non è mai stato raggiunto e quindi la tua soluzione afferma che siccome il suo tmin è 0 allora quello di 3 è 1.