#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n, m;
int g[N][N];
int d[N];
bool st[N];

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        st[t] = true;

        for(int j = 1; j <= n; j++)
            d[j] = min(d[j], d[t] + g[t][j]);
    }
    return d[n];
}

int main()
{
    while (cin >> n >> m)
    {
        memset(g, 0x3f, sizeof g);
        memset(st, false, sizeof st);
        if(n == 0 && m == 0) break;
        while( m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            g[a][b] = c;
            g[b][a] = c;
        }
        cout << dijkstra() << endl;
    }
    return 0;
}

堆优化：

#include <bits/stdc++.h...