#include<algorithm>
#include<iostream>
#include<sstream>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cctype>
#include<deque>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>

using namespace std;

const double ESP = 1e-8;
const double PI  = acos(-1.0);
const double E   = exp(1.0);
const int    INF = (1<<31)-1;

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;

struct node
{
    int x;
    int y;
};
template<class Ele,class Wei> struct edge
{
    Ele u;
    Ele v;
    Wei w;
};

#define findMax(a,x,y) (a[x]>a[y]?x:y)
#define findMin(a,x,y) (a[x]<a[y]?x:y)
#define Loop(i,n) for(int i=0;n-i>0;i++)
#define Less(a,b) ((b-a)>ESP)
#define More(a,b) ((a-b)>ESP)
#define Equl(a,b) (fabs(a-b)<ESP)

#define SIZE 300000

int n,t;
edge<int,int> a[SIZE];
int dist[SIZE]={0};

int x,y,z,tot=0;

int bellman_ford(void)
{
    for(int i=1;n-i>0;i++) dist[i]=INF;
    for(int i=1;n-i>0;i++)
    {
        bool ok=false;
        for(int j=0;tot-j>0;j++)
        {
            if(dist[a[j].v]!=INF&&dist[a[j].u]>dist[a[j].v]+a[j].w)
            {
                ok=true;
                dist[a[j].u]=dist[a[j].v]+a[j].w;
            }
        }
        if(!ok) break;
    }
    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[tot].u=x-1;
        a[tot].v=y-1;
        a[tot++].w=z;
        
        a[tot].u=y-1;
        a[tot].v=x-1;
        a[tot++].w=z;
    }
    printf("%d\n",bellman_ford());
    //system("pause");
    return 0;
}

• 再来个，SPFA，79MS，为毛还慢些？ (1246) speedcell4 2011-08-21 23:06:14
  • 你去攒人品吧，我的SPFA用pascal才16MS。。 (29) winL 2011-08-26 16:36:58