hdu-2544-最短路

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF (INT_MAX/2)
using namespace std;

int G[101][101];
int w[101];
int visited[101];
int n, m;
void Dijkstra();

int main()
{
    int a, b, c, i, j;
    while (scanf("%d %d", &n, &m) && (n || m))
    {
        for (i = 0; i <= n; i++)
            for (j = 0; j <= n; j++)
            {
                G[i][j] = i == j ? 0 : INF;
            }
        for (i = 0; i < m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            if (G[a][b] > c)
                G[a][b] = G[b][a] = c;
        }
        Dijkstra();
        printf("%dn", w[n]);
    }
    return 0;
}

void Dijkstra()
{
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= n; i++)
        w[i] = G[1][i];
    w[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int min = INF;
        int Vmin;
        for (int j = 1; j <= n; j++)
        {
            if (!visited[j] && w[j] < min&&i != j)
            {
                min = w[Vmin = j];
            }
        }
        visited[Vmin] = 1;
        for (int j = 1; j <= n; j++)
        {
            if (w[j] > w[Vmin] + G[Vmin][j])
                w[j] = w[Vmin] + G[Vmin][j];
        }
    }
}