题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1688
题意：第k短路，这里要求的是第1短路（即最短路），第2短路（即次短路），以及路径条数，最后如果最短路和次短路长度差1，则输出两种路径条数之和，否则只输出最短路条数。
思路：dijkstra变形，注意状态的转移，代码上附了注释，就不多说了．．
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 1010 3 using namespace std; 4 5 vector<pair<int, int> > mp[MAXN]; //***记录图 6 int dist[MAXN][3]; //***记录源点此时到 i 的距离状态即最短路距离和次短路距离 7 int cnt[MAXN][3]; //***记录该点作为最短路节点和次短路节点入队次数 8 int vis[MAXN][3]; //***标记该点的状态即在最短路中，在次短路中，或者未被标记 9 const int inf=0x3f3f3f3f; 10 11 struct node{ //***重载比较符使优先队列非升序排列 12 int point, value, tag;//***point记录点, value记录源点到此点的距离，tag标记次点是在最短路中或者在次短路中 13 friend bool operator< (node a, node b){ 14 return a.value!=b.value? a.value>b.value : a.point>b.point; 15 } 16 }; 17 18 int dijkstra_heap_k(int s){ 19 priority_queue<node> q; 20 memset(dist, 0x3f, sizeof(dist)); 21 memset(vis, false, sizeof(vis)); 22 memset(cnt, 0, sizeof(cnt)); 23 24 dist[s][1]=0; 25 cnt[s][1]=1; 26 q.push({s, 0, 1}); 27 28 while(!q.empty()){ 29 node u=q.top(); 30 int point=u.point; 31 int tag=u.tag; 32 q.pop(); 33 if(vis[point][tag]){ 34 continue; 35 }else{ 36 vis[point][tag]=1; 37 } 38 for(int i=0; i<mp[point].size(); i++){ 39 int v=mp[point][i].first; 40 int cost=mp[point][i].second; 41 42 //***找到比当前最短路更优的路径 43 if(!vis[v][1]&&dist[v][1]>u.value+cost){ 44 // 将之前的最短路变为次短路 45 if(dist[v][1]!=inf){ 46 dist[v][2]=dist[v][1]; 47 cnt[v][2]=cnt[v][1]; 48 q.push({v, dist[v][2], 2}); 49 } 50 //***更新最短路 51 dist[v][1]=u.value+cost; 52 cnt[v][1]=cnt[point][tag]; 53 q.push({v, dist[v][1], 1}); 54 }else if(!vis[v][1]&&dist[v][1]==u.value+cost){ 55 //***找到一条和当前最短路距离一样的路径，更新最短路数目 56 cnt[v][1]+=cnt[point][tag]; 57 }else if(!vis[v][2]&&dist[v][2]>u.value+cost){ 58 // 比最短路长，比当前次短路短 59 dist[v][2]=u.value+cost; 60 cnt[v][2]=cnt[point][tag]; 61 q.push({v, dist[v][2], 2}); 62 }else if(!vis[v][2]&&dist[v][2]==u.value+cost){ 63 // 和当前次短路一样长 64 cnt[v][2]+=cnt[point][tag]; 65 } 66 } 67 } 68 } 69 70 int main(void){ 71 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 72 int t, n, m; 73 cin >> t; 74 while(t--){ 75 cin >> n >> m; 76 while(m--){ 77 int x, y, z; 78 cin >> x >> y >> z; 79 mp[x].push_back({y, z}); //**记录有向图 80 } 81 int s, e; 82 cin >> s >> e; 83 dijkstra_heap_k(s); 84 if(dist[e][1]+1==dist[e][2]){ 85 cout << cnt[e][1]+cnt[e][2] << endl; 86 }else{ 87 cout << cnt[e][1] << endl; 88 } 89 for(int i=0; i<MAXN; i++){ 90 mp[i].clear(); 91 } 92 } 93 return 0; 94 }