题意：现在已有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 <iostream> #include <stdio.h> #include <string.h> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> 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<dij_node> 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]<disS[v]){ disS[v]=disS[idx]+rlength[k]; temp.init(v,disS[v]); q.push(temp); } } } } //其它点到t的距离 void dijkstra2(int v0){ int idx; dij_node temp,minNode; priority_queue<dij_node> 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]<disT[v]){ disT[v]=disT[idx]+rlength[k]; temp.init(v,disT[v]); q.push(temp); } } } } int main() { scanf("%d",&mark); for(int q=1;q<=mark;q++){ memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); //memset(exist,0,sizeof(exist)); tot1=0;tot2=0; scanf("%d%d",&n,&m); scanf("%d%d%d",&k,&s,&t); for(int p=1;p<=m;p++){ scanf("%d%d%d",&a,&b,&c); add1(a,b,c); add2(b,a,c);//反向图,因为要求出其它点到t点的最短路径，但如果用dijkstra求得话是t到其它点的，因此这里建立反向图 } dijkstra1(s); dijkstra2(t); ans=maxn; bool flag=false; for(int p=1;p<=k;p++){ scanf("%d%d%d",&a,&b,&c); if(disS[a]<maxn && disS[b]<maxn && disT[a]<maxn && disT[b]<maxn){ flag=true; ans=min(disS[a]+c+disT[b],ans); ans=min(disS[b]+c+disT[a],ans); ans=min(disS[t],ans); } } if(!flag) printf("-1 "); else printf("%d ",ans); } return 0; }