题意：现在已有m条单向路，问在给你的k条双向路中选择一条，使得s到t的距离最短

思路：设双向路两端点为a,b;长度为c。    

　　s到t的有三种情况：    

　　1：原本s到t的路径    

　　2：从s到a，a到b，b再到t的路径    

　　3：从s到b，b到a，a再到t的路径    

　　s到t的最短路径即三者之间的最小值，枚举每个双向路，取其中的最小值即可。   

　　用两次dijkstra，第一次求s到其它点的距离（正向图），第二次求t到其它点的距离（反向图）   

　  因为实际上我们要求的是其它点到t的距离，所以在第二次用dijkstra时，是在原先图的反向图基础上，求t到其它点的距离。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn=0x3f3f3f3f;int mark,n,m,k,s,t;int a,b,c;int ans;int disS[10005],disT[10005]; //disS[i]表示s到i的最短距离，disT[i]表示i到t的最短距离int vis[10005];int tot1=0,tot2=0;struct Road{ int next; int to;}road1[100010],road2[100010];int rlength[100010];int head1[10010],head2[10010];//建立正向图void add1(int x,int y,int l){ road1[tot1].next=head1[x]; road1[tot1].to=y; rlength[tot1]=l; head1[x]=tot1++;}//建立反向图void add2(int x,int y,int l){ road2[tot2].next=head2[x]; road2[tot2].to=y; rlength[tot2]=l; head2[x]=tot2++;}struct dij_node{ int u,dis; void init(int uu,int diss){ u=uu; dis=diss; } bool operator < (const dij_node& tmp) const { return dis> tmp.dis; //从大到小排 //优先级队列默认是取“最大”的，即排在最后的，如果从小到大排，则会取最大的出来。 //因此得从大到小排，这样才能取最小的出来。 }};//s到其它点的距离void dijkstra1(int v0){ int idx; dij_node temp,minNode; priority_queue
            
              q; memset(disS,maxn,sizeof(disS)); memset(vis,0,sizeof(vis)); disS[v0]=0; vis[v0]=1; temp.init(v0,disS[v0]); q.push(temp); while(!q.empty()){ minNode=q.top(); q.pop(); idx=minNode.u; vis[idx]=1; for(int k=head1[idx];k!=-1;k=road1[k].next){ int v=road1[k].to; if(!vis[v] && disS[idx]+rlength[k]
             
               q; memset(disT,maxn,sizeof(disT)); memset(vis,0,sizeof(vis)); disT[v0]=0; vis[v0]=1; temp.init(v0,disT[v0]); q.push(temp); while(!q.empty()){ minNode=q.top(); q.pop(); idx=minNode.u; vis[idx]=1; for(int k=head2[idx];k!=-1;k=road2[k].next){ int v=road2[k].to; if(!vis[v] && disT[idx]+rlength[k]