这道题就是让你求出有向图中最短路和比最短路长1的路的数量， 我们求出次短路和最短路的数量即可解决这道题
/* 求s到t的最短路与次短路（这里要求只比最短路多1）的条数之和 联想到最小，次小的一种更新关系： if(x<最小)更新最小，次小 else if(==最小)更新方法数 else if(x<次小)更新次小 else if(x==次小)更新方法数 同时记录s到u最短，次短路及方法数 用一个堆每次取最小的，更新完后再入堆 还是那个原理，第一次遇到的就是最优的，然后vi标记为真 方法数注意是加法原理，不是乘法 -- u -- v 所以是加法原理 / */
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 1000 + 10; const int inf = 0x3f3f3f3f; int N, M; struct edge { int v, c; }; vector<edge> G[maxn]; int S, F; struct Dij { int u, c, flog; bool operator< (const Dij& r) const { return c>r.c; } }; int dist[maxn][2], vis[maxn][2], dp[maxn][2]; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); memset(dp, 0, sizeof(dp)); dp[S][0]=1; dist[S][0]=0; priority_queue<Dij> que; que.push((Dij){S, 0, 0}); while(!que.empty()) { Dij tp = que.top(); que.pop(); int u = tp.u, flog = tp.flog; //使用这个状态更新其他的 if(vis[u][flog]) continue; vis[u][flog] = 1; for(int i=0; i<G[u].size(); i++) { int v = G[u][i].v, c = G[u][i].c; int w = dist[u][flog] + c; if(w < dist[v][0]) //更新次短路 最短路
{ if(dist[v][0] != inf) { dist[v][1] = dist[v][0]; dp[v][1] = dp[v][0]; que.push((Dij){v, dist[v][1], 1}); } dist[v][0] = w; dp[v][0] = dp[u][flog]; que.push((Dij){v, dist[v][0], 0}); } else if(w == dist[v][0]) //更新方法数 dp[v][0] += dp[u][flog]; else if(w < dist[v][1]) //更新次短路 { dist[v][1] = w; dp[v][1] = dp[u][flog]; que.push((Dij){v, dist[v][1], 1}); } else if(w == dist[v][1]) //更新方法数 dp[v][1] += dp[u][flog]; } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &N, &M); for(int i=0; i<=N; i++) G[i].clear(); for(int i=0; i<M; i++) { int u, v, t; scanf("%d%d%d", &u, &v, &t); G[u].push_back((edge){v, t}); //G[v].push_back((edge){u, t}); } scanf("%d%d", &S, &F); dijkstra(); if(dist[F][1]-dist[F][0] == 1) printf("%d ", dp[F][0]+dp[F][1]); else printf("%d ", dp[F][0]); } return 0; }