题目大意：
给出一个有向图，求从 顶点a 到 顶点b 的次短路。
第一行是2个正整数 n 和 e，表示该有向图的顶点数和边数。3 < n ≤ 5000 ， 3 < e < 40000 。顶点的编号是 1 ~ n 。
接下来 e 行，每行3个正整数 u , v 和 w ，表示一条从 顶点u 指向 顶点v 的弧，权值为 w
接下来是个正整数 Q，表示接下来有Q个询问。
接下来是Q行，每行2个正整数 a 和 b，表示询问从 顶点a 到 顶点b 的次短路长度。
每个询问输出一行结果：
如果不存在次短路，则输出 no route
否则，输出从 顶点a 到 顶点b 的次短路的长度
Sample Input
5 9
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
5 4 2
6
2 5
1 2
3 1
5 4
1 5
5 2
Sample Output
16
23
21
7
10
23
原本的dis[]数组记录最短路，改为开两个数组dis1[],dis2[]分别记录最短路和次短路
本题还有一个优化操作 因为是多个询问 所以另开一个邻接表记录已经搜索过的从某点出发的次短路
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define mp(i,j) make_pair(i,j) #define P pair<int,int> using namespace std; int n,e,dis1[5005],dis2[5005]; vector <P> vec[5005], got[5005]; // vec为图的邻接表 got为已搜过的次短路 void save(int a) { for(int i=1;i<=n;i++) /// 将已经得到的次短路结果记录下来 got[a].push_back(mp(i,dis2[i])); } void dijk(int a,int b) { memset(dis1,INF,sizeof(dis1)); memset(dis2,INF,sizeof(dis2)); priority_queue <P, vector<P>, greater<P> > q; // 使用pair好处在于 默认对.first排序 使用greater<>升序排序 q.push(mp(0,a)); dis1[a]=0; while(!q.empty()) { P u=q.top(); q.pop(); if(dis2[u.second]<u.first) continue; vector <P> ::iterator it; for(it=vec[u.second].begin();it!=vec[u.second].end();it++) { int w=u.first+(*it).first; int sec=(*it).second; if(w<dis1[sec]) { swap(dis1[sec],w); q.push(mp(dis1[sec],sec)); } if(w<dis2[sec]) { swap(dis2[sec],w); q.push(mp(dis2[sec],sec)); } } } if(dis2[b]==INF) printf("no route "); else printf("%d ",dis2[b]); save(a); } int main() { scanf("%d%d",&n,&e); while(e--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); vec[u].push_back(mp(w,v)); } int q; scanf("%d",&q); while(q--) { int a,b; scanf("%d%d",&a,&b); if(got[a].size()>0) { /// 已经搜过 直接从got中寻找结果 for(int i=0;i<got[a].size();i++) if(got[a][i].first==b) { if(got[a][i].second==INF) printf("no route "); else printf("%d ",got[a][i].second); break; } } else dijk(a,b); /// 否则dijk一下 } return 0; }