学步园

题目地址： http://poj.org/problem?id=2387

模板题，直接上代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

/*
freopen("input.txt",  "r", stdin);
freopen("output.txt", "w", stdout);
*/
const int INF=0x3f3f3f3f;
int n;
int edge[1005][1005],s[1005],dis[1005];

void Dijkstra(int be)
{
    int i,j,temp,k;
    for(i=1;i<=n;i++)
    {
        dis[i]=edge[be][i];
        s[i]=0;
    }
    s[be]=1;dis[be]=0;
    for(i=1;i<=n;i++)
    {
        temp=INF;k=1;
        for(j=1;j<=n;j++)
            if(!s[j]&&dis[j]<temp)
            {
                k=j;temp=dis[j];
            }
        s[k]=1;
        for(j=1;j<=n;j++)
            if(!s[j]&&dis[j]>dis[k]+edge[k][j])
                dis[j]=dis[k]+edge[k][j];
    }
}

int main()
{
    int i,j,t;
    while(cin>>t>>n)
    {
        memset(edge,INF,sizeof(edge));
        while(t--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(edge[a][b]>c)
                edge[a][b]=edge[b][a]=c;
        }
        Dijkstra(n);
        printf("%d\n",dis[1]);
    }
    return 0;
}