poj2387 Til the Cows Come Home 最短路径dijkstra算法

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

90

dijkstra算法模板题；
ＡＣ代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define inf 0xfffffff
using namespace std;
int p[1003][1003],flag[1003],dis[1003],mmin,n,t;
int dijkstra()
{
    memset(flag,0,sizeof(flag));
    for(int i=2;i<=n;i++)
    {
        dis[i]=p[1][i];
    }
    flag[1]=1;
    int pre;
    for(int i=1;i<=n;i++)
    {
        mmin=inf;
        for(int j=1;j<=n;j++)
        {
            if(flag[j]==0&&dis[j]<mmin)
            {
                mmin=dis[j];
                pre=j;
            }
        }
        if(mmin==inf)break;
        flag[pre]=1;
        for(int j=1;j<=n;j++)
        {
            if(flag[j]==0&&dis[pre]+p[pre][j]<dis[j])
            {
                dis[j]=dis[pre]+p[pre][j];
            }
        }
    }
}
int main()
{
    int a,b,l;
    while(scanf("%d%d",&t,&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                p[i][j]=inf;
            }
        }
        for(int i=0;i<t;i++)
        {
            scanf("%d%d%d",&a,&b,&l);
            if(l<p[a][b])
            {
                p[a][b]=p[b][a]=l;
            }
        }
        dijkstra();
        printf("%d\n",dis[n]);
    }
    return 0;
}