【单源最短路模板】 poj 2387

#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <memory.h>
using namespace std;
const int maxn=1005;
const int inf=1<< 30;
int s[maxn][maxn],dis[maxn],visit[maxn],n,m;
void dijstra()
{
    memset(visit,0,sizeof(visit));
    for(int i=1;i<=n;i++)
    dis[i]=inf;
    for(int i=1;i<=n;i++)
    dis[i]=s[1][i];
    for(int j=1;j<=n;j++)
    {
        int t=-1;
        for(int i=1;i<=n;i++)
        {
            if(!visit[i] && (dis[i]<dis[t]||t==-1) )
            t=i;
        }
        visit[t]=1;
        for(int i=1;i<=n;i++)
        {
            if(!visit[i] && s[i][t] && dis[i]>dis[t]+s[t][i])
            dis[i]=dis[t]+s[t][i];
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    s[i][j]=inf;
    for(int i=1;i<=n;i++)
    s[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(c<s[a][b])
        s[a][b]=s[b][a]=c;
    }
    dijstra();
//    int ans=-1;
//    for(int i=1;i<=n;i++)
//    {
//        if(ans==-1 || dis[i]>ans)
//        ans=dis[i];
//    }
    printf("%d",dis[n]);
    return 0;
}