Buongiorno a tutti!
Stavo provando a risolvere il problema “Sentieri bollenti” delle territoriali dell’anno scorso usando l’algoritmo di Dijkstra, però raggiungo solo la metà del punteggio massimo, in quanto nella metà dei casi l’output è errato.
Qualcuno può aiutarmi?
Grazie mille
Il codice è questo (dopo aver incluso gli header files limits.h, iostream e fstream):
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
int i, j, k, inizio, fine, Min, attuale;
int n;
in >> n;
int G[n][n];
inizio=0;
fine=n-1;
for(i=0; i<n; i++){
for(j=0; j<n; j++){
G[i][j]=INT_MAX;
}
}
int a;
int b;
in >> a >> b;
for(i=0; i<a; i++){
int c, d;
in >> c >> d;
G[c-1][d-1]=1;
}
for(i=0; i<b; i++){
int c, d;
in >> c >> d;
G[c-1][d-1]=10000;
}
int D[n];
for(i=0; i<n; i++){
D[i]=INT_MAX;
}
int P[n];
int V[n];
for(i=0; i<n ; i++){
P[i]=-1;
V[i]=0;
}
D[inizio]=0;
attuale=inizio;
while(attuale!=fine && Min!=INT_MAX){
Min=INT_MAX;
for(i=0; i<n; i++){
if(V[i]==0 && D[i]<Min){
Min=D[i];
attuale=i;
}
}
V[attuale]=1;
for(i=0; i<n; i++){
if(G[attuale][i] != INT_MAX && D[i]>D[attuale]+G[attuale][i]){
D[i]=D[attuale]+G[attuale][i];
P[i]=attuale;
}
}
}
out << (int)(D[n-1]/10000);
in.close();
out.close();
return 0;
}