> #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搜的最短路径。