Description:

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

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条商店到赛场的路线。
当N为0时，输入结束，该用例不被处理。

Output:

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

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(迪杰斯特拉)算法，Dijkstra算法求的是起点到图中其余任意一点的最短路径，写法和求最小生成树的Prim算法很像，在松弛步骤会有差别，因为Prim求的事其余顶点到已生成树的最小权值，而Dijkstra求的是从起点路过新添加顶点到达其余未添加顶点的最短路径。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;     // 正无穷（可以用memset）
const int maxn = 1e5+5;

struct connect {
    int v;              // 连接的顶点
    int time;            // 权值
};

int dis[maxn],N,M;              // N为顶点个数,M是输入连接组数,dis数组存最短路径
bool vis[maxn];                 // vis数组保存每个顶点的访问情况
vector<connect> Adj[maxn];      // Adj结构体数组存连接情况和权值

// Dijkstra算法求图中一点到另外所有点最小权值
void Dijkstra() {
    mem(dis, INF);              // 将dis数组初始化为正无穷
    mem(vis, 0);                // 将vis标记数组初始化为0
    dis[1] = 0;                 // 将起点到起点的最短路径设为0,这里1为起点
    for (int i = 0;i < N;++i) { // 循环n次求出起点到每个点的最短路径
        int u = -1,min = INF;   // u记录顶点,min记录最短路径
        for (int j = 1;j <= N;++j) { // 寻找dis数组中的最小值
            if (vis[j] == 0 && dis[j] < min) {  // 筛选没有被标记过并且起点到未被标记顶点最短路径
                u = j;          // 记录下筛选出的顶点
                min = dis[j];   // 记录起点到未被标记顶点的最短路径
            }
        }
        if (u == -1) {          // 如果没有找到符合要求的顶点则返回
            return;
        }
        vis[u] = 1;             // 将找出的顶点标记
        for (int j = 0;j < Adj[u].size();++j) {     // 循环更新顶点加入后起点到其它各个未标记顶点的最短路径
            int v = Adj[u][j].v;                    // 记录顶点为v
            if (vis[v] == 0 && dis[u] + Adj[u][j].time < dis[v]) {   // 顶点没有被标记过&起点到v顶点路径小于已记录路径
                dis[v] = dis[u] + Adj[u][j].time;        // 更新起始点到v顶点的最短路径
            }
        }
    }
}

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 输入顶点数和连接信息组数
    while (cin >> N >> M,N,M) {
        while (M--) {
            int A,B,C;
            cin >> A >> B >> C;
            connect add;
            add.v = B;
            add.time = C;
            Adj[A].push_back(add);
            // 无向图反向添加一次
            add.v = A;
            Adj[B].push_back(add);
        }
        Dijkstra();
        cout << dis[N] << endl;
        for (int i = 1;i <= N;++i) {
            Adj[i].clear();
        }
    }
    return 0;
}

优先队列优化Dijkstra的AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <functional>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 510;
const double eps = 1e-5;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;

struct connect {
    int v;
    int dis;
};

int n, m;
int dis[maxn];
vector<connect> Adj[maxn];

void Dijkstra() {
    priority_queue<P, vector<P>, greater<P> > que;
    mem(dis, INF);
    dis[1] = 0;
    que.push(P(0, 1));
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        if (p.second == n) {
            break;
        }
        for (int i = 0; i < Adj[v].size(); ++i) {
            connect e = Adj[v][i];
            if (dis[e.v] > dis[v] + e.dis) {
                dis[e.v] = dis[v] + e.dis;
                que.push(P(dis[e.v], e.v));
            }
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> m, n, m) {
        while (m--) {
            int Input_u, Input_v, Input_dis;
            cin >> Input_u >> Input_v >> Input_dis;
            connect add;
            add.v = Input_v;
            add.dis = Input_dis;
            Adj[Input_u].push_back(add);
            add.v = Input_u;
            Adj[Input_v].push_back(add);
        }
        Dijkstra();
        cout << dis[n] << endl;
        for (int i = 1; i <= n; ++i) {
            Adj[i].clear();
        }
    }
    return 0;
}