Come ha detto @zJack1342 il grafo non è bidirezionale devi leggere/scrivere da/su file di testo, basta che aggiungi:
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
Inoltre devi utilizzare i long long per memorizzare le distanze, altrimenti hai overflow.
Aggiustate queste 3 cose il tuo codice prenderà 70/100, soprattutto perché la tua implementazione di dijkstra è molto diversa da quella “classica e corretta”.
Innanzitutto il grafo lo devi memorizzare tramite le liste di adiacenza, ossia per ogni nodo x hai una lista che contiene tutti i nodi raggiungibili da x ed eventualmente la loro distanza. E poi il ragionamento di Dijkstra è il seguente.
- Hai una priority_queue che contiene {distanza, nodo} ordinata in ordine crescente per distanza.
- Hai un array che ti dice se hai già visitato un nodo(può essere un bool oppure per velocizzare l’algoritmo puoi salvarti per ogni nodo la distanza minore dal nodo sorgente). Per visitato si intende quando il nodo è il primo (ossia quello con distanza minore) nella pq, quando accade ciò per la prima volta significa che hai trovato il percorso minimo per quel nodo.
- Inserisci il nodo iniziale con distanza 0 nella pq.
- Fino a quando la pq non è vuota:
- Prendi il primo nodo dalla pq.
- Se è il nodo finale allora ritorna la distanza di quel nodo.
- Controlla che non sia già stato visitato.
- Se non lo è aggiungi nella pq con le relative distanze, i nodi che non sono già stati visitati raggiungibili dal nodo che hai appena estratto.
So che è uno spoiler gigante ma effettivamente ritengo più costruttivo mostrare un buon codice per Dijkstra, anche perché è un problema classicissimo quindi è meglio saperlo scrivere bene.
Questo è un mio template per risolvere Dijkstra:
template<typename T> T dijkstra(int N, int start, int end, vector<vector<pair<int,T>>> &graph){
vector<T> dist(N,-1);
priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<int,T>>> pq;
dist[start]=0;
pq.push({0,start});
while(!pq.empty()){
auto [d,node]=pq.top();
if(node==end)
return d;
pq.pop();
for(auto next:graph[node])
if(dist[next.first]==-1 || dist[next.first]>d+next.second){
dist[next.first]=d+next.second;
pq.push({dist[next.first],next.first});
}
}
return -1;
}
Ha come parametri il numero di nodi( da 0 a N-1), il nodo sorgente, quello destinazione, e poi graph dove graph[i] è una lista che contiene dei pair<nodo,distanza>, ossia i nodi raggiungibili dai i e la loro distanza dal nodo i.
Se il nodo destinazione non è raggiungibile da quello sorgente allora la funzione restituisce -1.
Inoltre invece di usare un array booleano per sapere se un nodo x è stato visitato o meno utilizza un vettore che indica la minima distanza di x dal nodo sorgente che è stata trovata sino ad ora. Il vantaggio è che mentre con l’array booleano puoi fare vis[node]=true; solo nel momento in cui arriva in cima alla pq, con la distanza tu puoi settarla direttamente nel momento in cui la inserisci nella pq, e questo implica che eviti che succeda qualcosa come: nella pq hai {dist=x, nodo=k} ma non è ancora in cima alla pq e quindi inserisci anche {dist=y (y>=x), nodo=k} quando non serve a nulla.