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

春游
春天阳光灿烂,小宋突然心血来潮想骑自行车去学校外面玩,但是到达目的地的路线不止一条,他想尽快的到达目的地,又能不需要骑太远的路, 你能帮助他吗?
输入格式:

输入包含一个测试数据,第一行有三个整数n(2 <= n <= 1000),途中可能经过的地点的个数,地点编号1~n;m(1 <= m <= 10000),为路径的条数;d(2 <= d <= n),目的地编号;其中学校为起点,默认为1。接下来m行: x y time dist , x y表示地点x,y是可以相互到达的,time,dist分别表示x到y或y到x的时间,距离。
输出格式:

按如下格式输出“花费的时间+空格+要骑的距离+空格+从学校到达目的地的路径”,路径中的两个地点之间以箭头(->)分隔。(具体见输出样例)
输入样例:

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的结果是
图片说明

查看全部
weixin_41777721
SYN_1
2019/03/28 13:07
  • c++
  • c语言
  • 点赞
  • 收藏
  • 回答
    私信

2个回复