最短路 HDU - 2544 (最短路基础题)

43 阅读 0 评论 29 点赞

我是靠谱客的博主调皮丝袜，最近开发中收集的这篇文章主要介绍最短路 HDU - 2544 (最短路基础题)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

D1. Coffee and Coursework (Easy version)

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的女装。所有同学都迫不及待的想穿上女装！所以现在负责搬运女装的工作人员想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Examples

Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2

题解:

直接上dijkstra板子即可

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1e2+10;
const int inf = 1<<30;

int V, E, cost[maxn][maxn];
int d[maxn];
bool used[maxn];
void dijkstra(int s){
    //求得从s出发到达各点的最短路径
    ms(used, 0);
    fill(d, d+maxn, inf);
    d[1] = 0;

    while(true){
        int u = 0;
        for(int v = 1; v <= V; v++)
            if(!used[v] && (u==0||d[v]<d[u])) u = v;
        if(u==0) break;
        used[u] = true;
        for(int v = 1; v <= V; v++)
            d[v] = min(d[v], d[u]+cost[u][v]);
    }

}
int main()
{
    while(cin>>V>>E && (E!=0&&V!=0)){
        fill_n(cost[0], maxn*maxn, inf);
        int u, v, c;
        for(int i = 1; i <= E; i++){
            cin >> u >> v >> c;
            cost[u][v] = cost[v][u] = c;
        }
        dijkstra(1);
        cout << d[V] << endl;
    }

	return 0;
}