#include  <stdio.h>
#include  <stdlib.h>

const  int  maxv=1010;
const  int  INF=36000;

int    vn,en;
int    cost[maxv][maxv];
bool flag;

struct {
       int  u;
       int  v;
}edge[10010];

void  init()
{
      for(int i=1;i<=vn;i++)
        for(int j=1;j<=vn;j++)
          cost[i][j]=INF;
}

void  change(int pre[],int k)
{
      if(pre[k]==k)   return ;
      cost[pre[k]][k]=INF;
      cost[k][pre[k]]=0-cost[k][pre[k]];
      change(pre,pre[k]);
}

int  dijkstra()
{
      
      int  *dist=new int[maxv];
      int  *pre=new int[maxv];
      int  s[maxv];
      int  i,j,u,mindis;
      for(i=1;i<=vn;i++){
        s[i]=0;
        dist[i]=cost[1][i];
        if(dist[i]<INF)  pre[i]=1;
          else  pre[i]=-1;
      }
      s[1]=1;  pre[1]=1;
      for(i=1;i<vn;i++){
         mindis=INF;
         u=-1;
         for(j=1;j<=vn;j++)
           if(!s[j]&&dist[j]<mindis){
                                     mindis=dist[j];
                                     u=j;
           }
         s[u]=1;
         for(j=1;j<=vn;j++)
           if(s[j]==0)
             if(cost[u][j]<INF&&dist[j]>dist[u]+cost[u][j]){
                dist[j]=dist[u]+cost[u][j];
                pre[j]=u;
             }
      }
      int  c=dist[vn];
      change(pre,vn);
      delete  []dist;
      delete  []pre;
      return  c;
}  

void relax(int dist[],int u,int v)
{
     if(dist[v]>dist[u]+cost[u][v])
        dist[v]=dist[u]+cost[u][v];
}

int  bf()
{
     int  *dist=new int [maxv];
     int  i,j;
     for(i=1;i<=vn;i++)
       dist[i]=cost[1][i];
     flag=true;
     for(i=1;i<vn&&flag;i++){
          for(j=0;j<en;j++)
            relax(dist,edge[j].u,edge[j].v);
          for(j=0;j<en;j++)
            if(dist[edge[j].v]>dist[edge[j].u]+cost[edge[j].u][edge[j].v]){
                              flag=false;  break;
            }
     }
     int c=dist[vn];
     delete []dist;
     return c;
}

int  main(void)
{
     int  min;
     while(scanf("%d%d",&vn,&en)==2){
        int u,v,w;
        init();
        for(int i=0;i<en;i++){
              scanf("%d%d%d",&u,&v,&w);
              edge[i].u=u;
              edge[i].v=v;
              cost[u][v]=cost[v][u]=w;
        }                
        min=dijkstra();
        min+=bf();
        printf("%d\n",min);
     }
          return 0 ;
}
                
          
第一遍是用Dijkstra搜的最短路径，反向后第二次用bellman_ford搜的最短路径。                           

• Re:不是大牛，貌似数组开小了的说 (2739) just_one 2011-01-09 14:58:22