#include<iostream>
#include<queue>

using namespace std;

#define SIZE 10000
#define INF  ((1<<31)-1)

struct edge
{
    int u;
    int v;
    int w;
}a[SIZE];
bool v[SIZE];
int dist[SIZE];
queue<int> node;

int t,n;
int x,y,z,Ne=0;

void Init(int s0)
{
    memset(v,false,sizeof(v));
    for(int i=0;n-i>0;i++) dist[i]=INF;
    dist[s0]=0; v[s0]=true;
    node.push(s0);
}
int SPFA(int s0)
{
    Init(s0);
    while(!node.empty())
    {
        int now=node.front();node.pop();v[now]=false;
        for(int i=0;Ne-i>0;i++)
        {
            if(a[i].u==now&&dist[a[i].v]>dist[a[i].u]+a[i].w)
            {
                dist[a[i].v]=dist[a[i].u]+a[i].w;
                if(v[a[i].v]==false)
                {
                    v[a[i].v]=true;
                    node.push(a[i].v);
                }
            }
        }
    }
    return dist[n-1];
}   
int main()
{
    scanf("%d %d",&t,&n);
    for(int i=0;t-i>0;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        a[Ne].u=x-1;
        a[Ne].v=y-1;
        a[Ne++].w=z;
        
        a[Ne].u=y-1;
        a[Ne].v=x-1;
        a[Ne++].w=z;
    }
    printf("%d\n",SPFA(0));
    //system("pause");
    return 0;
}

• 你去攒人品吧，我的SPFA用pascal才16MS。。 (29) winL 2011-08-26 16:36:58