dijstra最短路

*路程 HDU - 1874 *

今天稀的泥心情很好，没有带背包就出门了。然而他出门之后发现，由于自己之前铺的路太多了，有的路可能要绕很远才能到热的油的家。

已知稀的泥和热的油分别居住在的小区，以及稀的泥用稀的泥铺的所有道路，请你计算出稀的泥沿自己铺的路至少要走多远才能到热的油的小区。
Input
题目包含多组数据。

每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有小区的数目和稀的泥铺的道路的数目。小区分别以0～N-1编号。

接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示小区A和小区B之间有一条长度为X的双向道路。

再接下一行有两个整数S,T(0<=S,T<N)，分别代表稀的泥和热的油居住的小区。

Output
对于每组数据，请在一行里输出稀的泥最短需要走的距离。如果不存在从S到T的路线，就输出-1.

Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
Hint
不要问干的土在哪里。干的土在二基楼迷路了。

#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int inf = 0x7ffffff;
const int N = 210;
int g[N][N];
int s, e;
int d[N];
bool vis[210];
int n, m;
void dij(int x) {
    memset(vis, false, sizeof(vis));
    fill(begin(d), end(d), inf);
    d[x] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min = inf;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && d[j] < min) {
                u = j;
                min = d[j];
            }
        }
        if (u == -1)return;
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (!vis[v] && g[u][v] != inf) {
                if (d[u] + g[u][v] < d[v])d[v] = d[u] + g[u][v];
            }
        }
    }
}
int main()
{
    while (cin >> n >> m) {
        int x, y, z;
        fill(g[0], g[0] + N * N, inf);
        for (int i = 0; i < m; i++) {
            cin >> x >> y >> z;
            if(g[x][y]>z)//重点注意取最小的
            g[x][y] = g[y][x] = z;
        }
        cin >> s >> e;
        dij(s);
        if (d[e] == inf)cout << "-1" << endl;
        else cout << d[e] << endl;
    }
}