Stavo provando l’algoritmo Dijkstra ma mi da quest’errore, come risolvo?
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000
int M,N;
vector<pair<int, int> > adj[MAXN];
long long dist[MAXN];
int visto[MAXN];
void dijkstra(int inizio,int fine){
int u;
for(u=0; u<=N; u++) dist[u]=9999999;
dist[inizio]=0;
priority_queue<pair<int, int> > pq;
pq.push(make_pair(0,inizio));
while(!pq.empty()){
int s=pq.top().second;
pq.pop();
if(s==fine) break;
if(visto[s]) continue;
visto[s]=1;
for(u=0;u<adj[s].size();u++){
int next = adj[s][u].second;
int Peso = adj[s][u].first;
if(dist[s]+Peso<dist[next]){
dist[next] = dist[s]+Peso;
pq.push(make_pair(-dist[next], next));
}
}
}
}
int main(void)
{
int i,rad, end;
int a,b,w;
cin >> N >> M;
cin >> rad >> end;
for(i=0;i<M; ++i){
cin >> a >> b >> w;
adj[a].push_back(make_pair(w,b));
}
int u;
dijkstra(rad,end);
cout << dist[end] << endl;
return 0;
}
Input ed output devono essere effettuati utilizzando rispettivamente input.txt ed output.txt, inoltre devi incrementare di 1 il valori di MAXN altrimenti potresti accedere a memoria non allocata ed infine devi aumentare quel 9999999, io personalmente con i long long li setto a 1e18.
1 Mi Piace
ok grazie mille, ha funzionato. Tuttavia non capisco 2 cose, 1 il perchè di farlo tramite file, di solito pure se lasciavo commentate quelle due righe funzionava lo stesso, l’altra invece p quell 1e18, cioè immagino sia 1 * 10^18 ma serve una libreria particolare per farlo oppure no? avendo #include <bits/stdc++.h> ovviamente non servirebbe saperlo ma è per curiosità. Ah un’ ultima cosa è perchè 10001? dice che N deve essere compreso uguale tra 1 e 10000
Per quanto riguarda il file, prima si usavano quelli invece di stdin e stdout, e l’esercizio in questione è vecchio.
1e18 corrisponde a 10^18 e non serve nessuna libreria .
Se allocchi un array di N celle puoi indicizzare da 0 a N-1, essendo i nodi 1 based sforeresti con V[MAXN]
scusa ancora, cosa vuol dire che sono 1 based?
L’identificativo dei nodi va da 1 a N
1 Mi Piace
ok grazie ancora (parentesi per i 20 caratteri)