HDU-2544-最短路

这题没什么要注意的，只要建模没问题，代码其实OK的。
这题原点和终点是固定的，也就省了设置变量了。
这题的模型是无向带权的图，我们建立双向的边就可以啦。

#include <stdio.h>
#include <string.h>
const int INF = 1 << 30;
int n, m,a,b,c;
int w[110][110],d[110];
bool vis[110];

void Dijkstra()
{
    for (int i = 1; i <= n;i++) {
        d[i] = w[1][i];
    }
    d[1] = 0;
    vis[1] = 1;
    for (int i = 1; i < n;i++) {
        int min = INF,x;
        for (int j = 1; j <= n;j++) {
            if (!vis[j]&&d[j]<min) {
                x = j;
                min = d[j];
            }
        }
        vis[x] = 1;
        if (min==INF)
            break;
        for (int j = 1; j <= n;j++) {
            if (!vis[j]&&d[j]>d[x]+w[x][j]) {
                d[j] = d[x] + w[x][j];
            }
        }
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)&&n+m) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n;i++) {
            for (int j = 1; j <= n;j++)
                w[i][j] = INF;
        }
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            w[a][b]=w[b][a]=c;
        }
        Dijkstra();
        printf("%d
", d[n]);
    }
    return 0;
}