统计次短路数量
求最短路与次短路（只与最短路长度相差 \(1\) 的次短路）数量之和。
最短路
首先回顾我们如何统计最短路数量，我们使用 \(cnt[j]\) 表示从源点到 \(j\) 的最短路数量。
dist[j] > dist[v] + w[i]如果当前点 \(v\) 更新 \(dist[j]\) 的时候，发现从 \(v\) 出发是一个更优的选择，那么更新 \(cnt[j] = cnt[v]\)；dist[j] == dist[v] + w[i]如果当前点 \(v\) 更新 \(dist[j]\) 的时候，发现从 \(v\) 出发也是一条可行的最短路，那么更新 \(cnt[j] ++\)；
想法
如果只有一个 \(dist[i]\) 数组不好表示次短路。
不妨运用 拆点的思想，将其扩展成二维的 \(dist[i][j](j\in \{0, 1\})\) 表示 ：
- \(j = 0\) 时表示从源点到 \(i\) 的最短路的距离；
- \(j = 1\) 时表示从源点到 \(i\) 的次短路的距离。
同理，\(cnt[i][j](j\in \{0, 1\})\) 表示 ：
- \(j = 0\) 时表示从源点到 \(i\) 的最短路的数量；
- \(j = 1\) 时表示从源点到 \(i\) 的次短路的数量。
思路
在想法的基础上，我们照葫芦画瓢地进行 \(cnt[i][j](j\in \{0, 1\})\) 的计算。
- \(dist[i][0] > nowd + w\)，其中 \(nowd\) 表示当前点 \(dist[id][type]\) 的值，\(w\) 表示 \(i\) 到 \(j\) 的边权。即当前点出发时一个比目标点最短路更优的选择，那么从当前点出发的路径就自然地变成了目标点的新最短路，原来的最短路就变成了当前的次短路；
dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0] dist[j][0] = nowd + w, cnt[j][0] = nowc // nowc 表示 cnt[id][type]
-
\(dist[j][0] = nowd + w\) 即发现了一条新的可行的最短路，那么将其纳入彀中
cnt[j][0] += nowc； -
\(dist[j][1] > nowd + w\) 即发现了一条更优的次短路，此时：
- 如果比最短路优就更新最短路（实现的时候直接
else if掉就没有这种情况了）； - 如果没有最短路优，就只更新次短路即可 。
dist[j][1] = nowd + w, cnt[j][1] = nowc - 如果比最短路优就更新最短路（实现的时候直接
-
\(dist[j][1] = nowd + w\) 即发现了一条新的可行的次短路，那么将其纳入彀中
cnt[j][0] += nowc。
码来！
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
struct qwq
{
int x, type, y;
bool operator> (const qwq& W) const
{
return y > W.y;
}
};
int dist[N][3];
bool st[N][3];
int S, F;
vector<PII> g[N]; // vector存图方便快捷
int cnt[N][3];
void init(int n)
{
for(int i = 1; i <= n; i ++) g[i].clear();
memset(st, 0, sizeof st);
}
int dijkstra() // 求1号点到n号点的最短路距离
{
memset(dist, 0x3f, sizeof dist);
cnt[S][0] = dist[S][0] = 1;
priority_queue<qwq, vector<qwq>, greater<qwq>> q;
q.push({S, 0, 0});
while (q.size())
{
auto t = q.top();
q.pop();
int id = t.x;
if (st[id][t.type]) continue;
st[id][t.type] = true;
for(auto i : g[id])
{
int j = i.x;
int &nowd = dist[id][t.type];
int &nowc = cnt[id][t.type];
if(dist[j][0] > nowd + i.y)
{
dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
dist[j][0] = nowd + i.y, cnt[j][0] = nowc;
q.push({j, 1, dist[j][1]}); // 要记得把更新后的点丢进堆里
q.push({j, 0, dist[j][0]});
}
else if(dist[j][0] == nowd + i.y)
cnt[j][0] += nowc;
else if(dist[j][1] > nowd + i.y)
{
dist[j][1] = nowd + i.y, cnt[j][1] = nowc;
q.push({j, 1, dist[j][1]});
}
else if(dist[j][1] == nowd + i.y)
cnt[j][1] += nowc;
}
}
if(dist[F][0] == dist[F][1] - 1) return (cnt[F][0] + cnt[F][1]); // 判断次短路是否与最短路相差1，删掉这行就是次短路模板
return cnt[F][0];
}
inline int read()
{
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
int main()
{
int T;
T = read();
while(T --)
{
int n, m;
n = read(), m = read();
init(n);
for(int i = 1; i <= m; i ++)
{
int a, b, c;
a = read(), b = read(), c = read();
g[a].push_back({b, c});
}
S = read(), F = read();
printf("%d\n", dijkstra());
}
return 0;
}