题意：给定一张图，从1到n，若能随便去除一条路，问最短路？

注意：两点可能存在多条路，这时 事实上只要保存下第一短和第二短的，然后在枚举的时候每次去除一条换上第二短的路。。。。。

这样最后就能得到ans。

（若存在某种方法使得1不能到n，则break，print -1 ）

1 #include
      
         2  #include
       
          3  #include
        
           4  #include
         
            5  #include
          
             6  using namespace std;  7  const int maxn = 1105;  8  const int maxm = 110005;  9  const int inf = 1000000000; 10  struct node{ 11      int u,val,next; 12  }edge[ maxm ]; 13  int head[ maxn ],cnt; 14  int n; 15  int dis[ maxn ],vis[ maxn ]; 16  struct node3{ 17      int u,val; 18  }path[ maxn ]; 19  struct node2{ 20      int x,y,val; 21  }road[ maxm ]; 22  void init(){ 23      cnt=0; 24      memset( head,-1,sizeof( head )); 25     // for( int i=1;i<=n;i++ ) 26         // for( int j=1;j<=n;j++ ) 27             // mat[i][j]=inf; 28  } 29  void addedge( int a,int b,int c ){ 30      edge[ cnt ].u=b; 31      edge[ cnt ].val=c; 32      edge[ cnt ].next=head[ a ]; 33      head[ a ]=cnt++; 34  } 35  void spfa( int s ){ 36      for( int i=1;i<=n;i++ ){ 37          dis[i]=inf; 38          vis[i]=0; 39          path[i].u=-1; 40      } 41      queue
           
            q; 42 while( !q.empty() ) 43 q.pop(); 44 vis[s]=1; 45 dis[s]=0; 46 q.push( s ); 47 while( !q.empty() ){ 48 int now=q.front(); 49 q.pop(); 50 vis[ now ]=0; 51 for( int i=head[ now ];i!=-1;i=edge[i].next ){ 52 int next=edge[i].u; 53 if( dis[next]>dis[now]+edge[i].val ){ 54 dis[next]=dis[now]+edge[i].val; 55 path[next].u=now; 56 path[next].val=edge[i].val; 57 if( vis[next]==0 ){ 58 vis[next]=1; 59 q.push(next); 60 } 61 } 62 } 63 } 64 return ; 65 } 66 void change( int pos,int x,int y,int pre,int nxt ){ 67 //int tmp_max=inf,k; 68 for( int i=head[ x ];i!=-1;i=edge[ i ].next ){ 69 if( edge[i].u==y&&edge[i].val==pre ){ 70 edge[i].val=nxt; 71 break;//注意这个break，如果某两个点之间存在两条相同长度的路径，这是只要改变其中一条即可！！！ 72 } 73 } 74 75 } 76 int main(){ 77 int ca; 78 scanf("%d",&ca); 79 while( ca-- ){ 80 scanf("%d",&n); 81 int m; 82 scanf("%d",&m); 83 int a,b,c; 84 init(); 85 while( m-- ){ 86 scanf("%d%d%d",&a,&b,&c); 87 addedge( a,b,c ); 88 addedge( b,a,c ); 89 } 90 spfa( 1 ); 91 cnt=0; 92 for( int i=n;i!=-1;i=path[i].u ){ 93 road[ cnt ].x=i; 94 road[ cnt ].y=path[i].u; 95 road[ cnt ].val=path[i].val; 96 cnt++; 97 }//先spfa出最短路的路径 98 int ans=dis[n]; 99 if( ans==inf ){100 printf("-1\n");101 continue;102 }103 for( int i=0;i
            
             ans&&dis[n]!=inf ){114 ans=dis[n];115 }116 change( i,road[i].x,road[i].y,nxt,pre/*mat[road[i].x][road[i].y]*/ );117 change( i,road[i].y,road[i].x,nxt,pre/*mat[road[i].x][road[i].y]*/ );118 ////每次改变原最短路中的某一条，如果这两点之间存在多条路，则挑第二短的路再spfa即可！！！119 }120 if( ans==inf )121 printf("-1\n");122 else123 printf("%d\n",ans);124 }125 return 0;126 }