最短路 (dijkstra)

2017年11月9日 2点热度 0条评论 来源: Guuuuuu老师儿


  

最短路

有一天雪菜和东马一起组队写代码,在连续WA了233次后,东马忍不住站起来大发雷霆,对雪菜说,

 

明明是我先写的,A题也好,调试也好,可是为什么会这样呢,你为什么WA的这么熟练啊!连这种简单题怎么都不会做?

 

我跟你讲,我可是身经百战了,哪个类型的题我没见过?你知道集训队的CerberuX菊苣吧,就是那个河老师,比你不知道高到哪里去啦,我和他谈笑风生啊!

 

监考老师正巧就是CerberuX老师,他听到了东马的声音注意到了他们,准备走过去提醒他们比赛时不要站起来大声讲话。可是为了避免走动时影响其他同学,他准备找一条最短的路径过去。

 

由于机房非常非常大,而且机器的布局也不规律,所以不同机位之间不一定有通路可以直接走过去,CerberuX一时半会找不出这样的一条路线,你能帮助他找到这条路并计算出需要多长时间才能走过去吗?

Input

输入包括多组数据。
 
每组数据第一行是两个整数N、M(N<=100,M<= 10000),
 
N表示集训队机房内电脑数量,标号为1的是CerberuX的位置,标号为N的是东马和雪菜的位置,M则表示机房内有多少条路。
 
N = M = 0表示输入结束。
 
接下来M行,每行包括3个整数A,B,C(1 <= A,B <= N,1 <= C <=1000),表示在机位A与机位B之间有一条路,CerberuX需要C分钟的时间走过这条路。

Output

对于每组输入,输出一行,表示CerberuX从1号位置走到东马和雪菜位置的最短时间。如果CerberuX不能从1号位置走到东马和雪菜的位置,输出-10086。

Sample Input

2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0

Sample Output

3 2

Hint

CerberuX!


最短路模板题
code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
int mp[105][105];
int vis[105];
int dis[105];
int n,m;
void Dijkstra(int s){
    memset(vis,0,sizeof(vis));
    int i;
    for(i = 1; i <= n; i++){
        dis[i] = mp[s][i];
    }
    dis[1] = 0;
    vis[1] = 1;
    int j;
    for(i = 1; i < n; i++){
        int mind = INF;
        int u = -1;
        for(j = 1; j <= n; j++){
            if(!vis[j]&&dis[j]<mind){
                mind = dis[j];
                u = j;
            }
        }
        if(u==-1)break;
        vis[u] = 1;
        for(j = 1; j <= n; j++){
            if(!vis[j]&&dis[j] > dis[u]+mp[u][j])
                dis[j] = dis[u] + mp[u][j];
        }
    }
    if(dis[n]==INF)printf("-10086\n");
    else printf("%d\n",dis[n]);
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        if(n==0&&m==0)break;
        int i;
        memset(mp,INF,sizeof(mp));
        for(i = 1; i <= m; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b] = c;
            mp[b][a] = c;
        }
        Dijkstra(1);
    }
    return 0;
}
    原文作者:Guuuuuu老师儿
    原文地址: https://blog.csdn.net/codeswarrior/article/details/78482860
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。