The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-A. Customized Shortest Path 题目 A. 定制最短路（分步 dp 拓展解决这个计数问题） · znzryb
## 题目大意
**题目描述**
给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其初始边权（遍历代价）为 $w_i$。
你可以将所有边的边权同时增加一个非负实数 $k$。
请问：存在多少条从顶点 $1$ 到顶点 $n$ 的不同路径，使得至少存在一个 $k$ 的值，能够让该路径成为从顶点 $1$ 到顶点 $n$ 的最短路之一？
两条路径被认为是不同的，当且仅当它们包含的边数不同，或者在某一步经过了不同编号的边（即使连接的顶点相同）。
由于答案可能很大，请输出可能成为最短路的不同路径数量对 $998244353$ 取模后的结果。
**输入格式**
第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5000$，$1 \le m \le 5000$），分别表示图的顶点数和边数。
接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），描述了一条连接 $u_i$ 和 $v_i$、边权为 $w_i$ 的无向边。
保证所有测试用例的 $n$ 之和不超过 $5000$，$m$ 之和不超过 $5000$。
**输出格式**
对于每个测试用例，输出一个整数，表示符合条件的路径数量对 $998244353$ 取模的值。
**样例输入**
```
3
3 4
1 2 1
1 2 1
2 3 1
2 3 1
5 6
1 5 3
1 2 1
2 5 2
1 3 1
3 4 1
4 5 1
8 9
1 2 1
1 3 5
2 6 1
6 4 1
3 4 1
3 5 1
4 8 5
5 7 1
7 8 1
```
**样例输出**
```
4
3
4
```
**样例解释**
以第一个测试用例为例，图中有 $3$ 个顶点和 $4$ 条边。
顶点 $1$ 和 $2$ 之间有两条权值为 $1$ 的平行边。
顶点 $2$ 和 $3$ 之间有两条权值为 $1$ 的平行边。
无论非负实数 $k$ 取何值，从 $1$ 到 $3$ 的最短路径一定由一条连接 $1, 2$ 的边和一条连接 $2, 3$ 的边组成（共经过 $2$ 条边，总权值为 $2+2k$）。包含边的组合情况共有 $2 \times 2 = 4$ 种不同路径，因此答案为 $4$。
对于第二个测试用例：
有三条从 $1$ 到 $5$ 的主要路径方案：
路径一：直接走边 $1 \leftrightarrow 5$，包含 $1$ 条边，初始总权值为 $3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + k$。
路径二：依次经过 $1 \leftrightarrow 2 \leftrightarrow 5$，包含 $2$ 条边，初始总权值为 $1 + 2 = 3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + 2k$。
路径三：依次经过 $1 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5$，包含 $3$ 条边，初始总权值为 $1 + 1 + 1 = 3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + 3k$。
可以发现，当 $k=0$ 时，这三条路径的总代价都是 $3$，均能够成为从 $1$ 到 $5$ 的最短路。因此可能的路径总数为 $3$。
对于第三个测试用例，答案经过相同的逻辑推导，共有 $4$ 条路径有可能在某个 $k$ 值下成为最短路。
## 思路讲解
```cpp
vector<ll> mndis(N + 2, INF);
mndis[1] = 0;
vector<ll> cntRoute(N + 2);
// 起始值
cntRoute[1] = 1;
// 说白了，由于我们采用一维数组设计，因此就是滚动数组
// 如果开两维，就是有一维是 step
vector<ll> step_mndis(N + 2, INF), step_sp_cnt(N + 2);
for (int step = 1; step <= N - 1; ++step) {
// 在 step 步下，到达该点所需的最短路径长度
// 在 step 步下，到达该点的最短路径长度
vector<ll> lmndis(N + 2, INF), lcntRoute(N + 2);
for (int u = 1; u <= N; ++u) {
for (auto [to,w]: g[u]) {
if (mndis[u] + w > lmndis[to]) {
continue;
}
if (mndis[u] + w == lmndis[to]) {
lcntRoute[to] += cntRoute[u];
lcntRoute[to] %= mod;
continue;
}
if (mndis[u] + w < lmndis[to]) {
lcntRoute[to] = cntRoute[u];
// lcntRoute[to] %= mod;
lmndis[to] = mndis[u] + w;
}
}
}
swap(lcntRoute, cntRoute);
swap(lmndis, mndis);
step_mndis[step] = mndis[N];
step_sp_cnt[step] = cntRoute[N];
}
```
超出可能成为最小值的那些直线，可以使用凸包 $O(n)$ 的解决，也可以使用 naive 的方法 $O(n^2)$ 解决。
```cpp
vector<Point> hull;
for (int step = 1; step <= N - 1; ++step) {
hull.push_back(Point(step, step_mndis[step]));
}
hull = make_convex_hull(hull, true);
ll ans = 0;
for (int i = 0; i < SZ(hull); ++i) {
auto [step,dummy] = hull[i];
if (i == 0) {
ans += step_sp_cnt[step];
ans %= mod;
continue;
}
// 我们只要下凸包
if (dummy > hull[i - 1].y) {
break;
}
ans += step_sp_cnt[step];
ans %= mod;
}
```
## AC代码
AC
[https://qoj.ac/submission/2147487](https://qoj.ac/submission/2147487)
AC
[https://codeforces.com/gym/106139/submission/367332908](https://codeforces.com/gym/106139/submission/367332908)
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）
感觉最近的 ai 属于是纯纯傻逼啊，这么简单的 bfs 都不会，非要用 dp，真的是纯纯傻逼，问题是 dp 很难解决这个问题！！！
也不能说是他们的问题。
