学步园

裸的最短路.

#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
typedef struct node
{
    int v,w;
    node(){}
    node(int _v, int _w):v(_v),w(_w){}
}node;
vector<node> g[MAXN];
int n,m,d[MAXN];
bool vis[MAXN];

int Dijkstra(int s, int t)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    d[s] = 0;
    for(int i=0;i<n;i++)
    {
        int k = 0,mi = INF;
        for(int j=1;j<=n;j++)//手残写成i<=n...
        {
            if(!vis[j] && d[j]<mi)
            {
                mi = d[j];
                k = j;
            }
        }
        if(!k)  break;//这题这句不需要
        vis[k] = true;
        for(int j=0,v,w;j<g[k].size();j++)
        {
            v = g[k][j].v, w = g[k][j].w;
            if(!vis[v] && d[v]>d[k]+w)
                d[v] = d[k] + w;
        }
    }
    return d[t];
}

int main()
{
    while(scanf("%d %d",&n,&m)==2 && (n+m))
    {
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<=m;i++)
        {
            int a,b,w;
            scanf("%d %d %d",&a,&b,&w);
            g[a].push_back(node(b,w));
            g[b].push_back(node(a,w));
        }
        printf("%d\n",Dijkstra(1,n));
    }
}