胡扯
看到这道题写最短路也写网络流，正好拿过来写写
难度很低，大佬轻喷/kk
思路
最短路可行边+网络最大流
手残写错了几个地方调了半个上午
题意就是找题目给定起点终点之间最短路的条数。
有一个很显然的性质，设起点为 (s), 终点为 (t)， (dis_{u,v}) 表示 (u) 到 (v) 的最短路，(val_{x,y}) 表示边 ((x,y)) 的长度，则对于一条可以在最短路上的边((x,y))，一定有 (dis_{s,x}+val_{x,y}+dis_{y,t}=dis_{s,t})。
有了这个性质，我们就可以将最短路上的边重新建图，边的流量为 (1)，然后在图上跑最大流，得到的最大流就是最短路的条数。
求最短路可以用 (Dij) 跑出 (s) 到每个点的最短路，同时建反向边，跑出 (t) 到每个点的最短路（实际上是每个点到 (t) 的最短路），再进行上述判断即可。
重边不用判，因为说不定这条重边也可以在最短路上。
代码
注释不删了，好让自己明白自己有多菜
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e5 + 11;
const int B = 2e3 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct edge { int to, nxt, val; } e[A << 1];
int n, m, cnt, flag[B][B], endd, head[2][A], dis[2][A], vis[A];
inline void add(int tg, int from, int to, int val) {
e[++cnt].to = to;
e[cnt].val = val;
e[cnt].nxt = head[tg][from];
head[tg][from] = cnt;
}
struct node {
int x, y;
bool operator < (const node &b) const {
return y > b.y;
}
};
inline void Dij(int s, int tg) {
priority_queue <node> Q;
while (!Q.empty()) Q.pop();
memset(vis, 0, sizeof(vis));
memset(dis[tg], inf, sizeof(dis[tg]));
dis[tg][s] = 0;
Q.push((node){s, 0});
while (!Q.empty()) {
int now = Q.top().x; Q.pop();
if (vis[now]) continue;
vis[now] = 1;
for (int i = head[tg][now]; i; i = e[i].nxt) {
int to = e[i].to;
if (dis[tg][now] + e[i].val < dis[tg][to]) {
dis[tg][to] = dis[tg][now] + e[i].val;
Q.push((node){to, dis[tg][to]});
}
}
}
// for (int i = 1; i <= n; i++) cout << dis[tg][i] << " ";
// puts("");
}
struct Max_flow {
struct edge { int to, nxt, val; } edd[A << 1];
int ccnt = 1, cur[A], inq[A], dep[A], hdd[A], vis[A];
inline void init() {
ccnt = 0;
memset(hdd, 0, sizeof(hdd));
memset(cur, 0, sizeof(cur));
}
inline void add(int from, int to, int val) {
edd[++ccnt].to = to;
edd[ccnt].val = val;
edd[ccnt].nxt = hdd[from];
hdd[from] = ccnt;
}
inline bool bfs(int s, int t) {
queue <int> Q;
for (int i = 1; i <= n; i++)
cur[i] = hdd[i], dep[i] = inf, inq[i] = 0;
Q.push(s), dep[s] = 0, inq[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop(), inq[x] = 0;
for (int i = hdd[x]; i; i = edd[i].nxt) {
int to = edd[i].to;
if (dep[x] + 1 < dep[to] && edd[i].val) {
dep[to] = dep[x] + 1;
if (!inq[to]) Q.push(to), inq[to] = 1;
}
}
}
return dep[t] != inf;
}
int dfs(int x, int flow) {
if (x == endd) return flow;
for (int i = cur[x], tmp = 0; i; i = edd[i].nxt) {
cur[x] = i;
int to = edd[i].to;
if (dep[to] == dep[x] + 1 && edd[i].val) {
if (tmp = dfs(to, min(edd[i].val, flow))) {
edd[i].val -= tmp, edd[i ^ 1].val += tmp;
return tmp;
}
}
}
return 0;
}
} Flow;
inline void solve() {
memset(flag, 0, sizeof(flag));
memset(head, 0, sizeof(head));
Flow.init();
cnt = 0;
n = read(), m = read();
int tot = 0;
for (int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
add(0, u, v, w);
add(1, v, u, w);
}
int s = read(), t = read();
Dij(s, 0), Dij(t, 1);
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << flag[i][j] << " ";
// }
// puts("");
// }
for (int i = 1; i <= n; i++) {
for (int j = head[0][i]; j; j = e[j].nxt) {
// cout << "ij " << i << " " << e[j].to << " ";
// cout << dis[0][i] << " " << e[j].val << " " << dis[1][e[j].to] << " " << dis[0][t] << '
';
if (dis[0][i] + e[j].val + dis[1][e[j].to] == dis[0][t]) {
Flow.add(i, e[j].to, 1);
Flow.add(e[j].to, i, 0);
}
}
}
endd = t;
int ans = 0, now = 0;
// cout << Flow.ccnt << '
';
while (Flow.bfs(s, t)) while (now = Flow.dfs(s, inf)) ans += now;
cout << ans << '
';
return;
}
signed main() {
int T = read();
while (T--) solve();
}