# 有关Dijkstra算法的一道基础的编程题，不知道无法AC的原因

``````7 8 7
1 2 1 1
1 3 1 1
2 4 1 2
3 4 1 1
4 5 1 2
4 6 1 1
5 7 1 1
6 7 2 1
``````

``````4 5 1->3->4->5->7
``````
``````#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define INF 100000
int n;
int tu[1005][1005];
int len[1005][1005];
int vist[1005];
int tim[1005];
int dist[1005];
int path[1005];

void dijkstra(){
while(1){
int min=INF,x=-1;
for(int i=1;i<n+1;i++){
if(vist[i]!=1&&tim[i]<min){
min=tim[i];
x=i;
}
}
if(x==-1) break;
vist[x]=1;

for(int i=1;i<n+1;i++){
if(vist[i]||!tu[x][i]) continue;
if(tim[i]>tim[x]+tu[x][i]){
tim[i]=tim[x]+tu[x][i];
dist[i]=dist[x]+len[x][i];
path[i]=x;
}
else if(tim[i]==tim[x]+tu[x][i]){
if(dist[i]>dist[x]+len[x][i]){
dist[i]=dist[x]+len[x][i];
path[i]=x;
}
}
}
}

}

int main(){

int m;int end;
cin>>n>>m>>end;
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
tu[a][b]=c;tu[b][a]=c;
len[a][b]=d;len[b][a]=d;
}

fill(tim,tim+1005,INF);
fill(dist,dist+1005,INF);
fill(path,path+1005,-1);
tim[1]=0;dist[1]=0;
dijkstra();

cout<<tim[end]<<" "<<dist[end]<<" ";

int f[n];int k=1;f[0]=end;
while(path[end]!=-1){
end=path[end];
f[k++]=end;
}

int flag=0;
while(k--) {
if(flag)printf("->");
printf("%d",f[k]);
flag=1;
}
}

``````

oj的结果是

2019/03/28 13:07
• c++
• c语言
• 点赞
• 收藏
• 回答
私信