Dijkstra(HDU 2544)

• 适合不含负权边的单源最短路
• S：已找到的到源点的集合
• dis[i]：顶点i到源点的最短路径距离
• 每次取不在S中dis最小的点v，将v加入S， 并更新各点dis值

---

伪代码
1.初始化S，将源点加入S
2.初始化dis，与源点有连接的为那条边的值，否则为无穷大

while（S不包含所有顶点）
{
         u=min{dis[u]|u不在S中}
         u加入S
         for（每个不在S中的点v&&dis[v]>dis[u]+w（uv））
               dis[v]=dis[u]+w（uv）;
}

---

时间复杂度为O（n^2），因为找S外的dis最小点要耗费O（n）
此处用堆来优化可降到O（nlgn）

---

HDU 2544
Problem 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条商店到赛场的路线。

---

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

---

思路：
用优先队列来优化最小距离的查找
优先队列中的每一项是表示该店的下标和dis的结构体
用二维数组来存图
定义一维数组visited存点是否被访问过，dis存距离源点的距离
首先每次执行时都要初始化这几个数组，visited全是0，dis全是一个超大的值，二维数组对角线0其他-1
dijkstra算法，将源点入队，并且源点的dis要设为0（这步容易漏），while循环，队列非空，并且终点还未被访问过
找出队列中优先级最高（即dis最小）且未被访问过点
访问设为是
对每个结点判断是否未被访问过与刚才找到的点是否有连接是否能使dis变小
如果可以更新dis，并入队
pop刚才访问的那个点

---

#include <iostream>
#include <queue>
#include <cstring>
#define N 110
#define INF 999999
using namespace std;
struct node {
    //优先队列中的结点
    int num;//点的编号
    int val;//到源点的距离

    friend bool operator<(node a, node b) {
        return a.val>b.val;
    }
};
int dis[N];//存到源点的距离
int edge[N][N];//存边的权值
int visited[N];//存是否被访问过
int v, e;
priority_queue<node> que;

int Dijkstra(int s, int t)
{
    //s源点，t终点
    node n;
    dis[s] = 0;//注意这部别漏了
    n.num = s; n.val = 0;
    que.push(n);
    while (!que.empty() && (!visited[t])) {
        while (visited[que.top().num]) que.pop();
        visited[que.top().num] = 1;
        for (int i = 1; i <= v; ++i) {
            if ((!visited[i]) && edge[que.top().num][i] != -1)
                if (dis[i]>dis[que.top().num] + edge[que.top().num][i]) {
                    dis[i] = dis[que.top().num] + edge[que.top().num][i];
                    n.num = i; n.val = dis[i];
                    que.push(n);
                }
        }
        que.pop();
    }
    return dis[t];
}
int main()
{
    cin >> v >> e;
    while (v + e) {
        memset(dis, INF, sizeof(dis));
        memset(edge, -1, sizeof(edge));
        memset(visited, 0, sizeof(visited));
        while (!que.empty()) que.pop();
        for (int i = 1; i <= v; ++i)
        {
            edge[i][i] = 0;
        }
        for (int i = 1; i <= e; ++i)
        {
            //读图而且重下标1开始存
            int beg, en, wgt;
            cin >> beg >> en >> wgt;
            edge[beg][en] = edge[en][beg] = wgt;
        }
        cout << Dijkstra(1, v) << endl;
        cin >> v >> e;
    }
    return 0;
}