The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-A. Customized Shortest Path 题目 A. 定制最短路（分步 dp 拓展解决这个计数问题）

题目大意

题目描述
给定一个包含 $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$ 值下成为最短路。

思路讲解

超出可能成为最小值的那些直线，可以使用凸包 $O(n)$ 的解决，也可以使用 naive 的方法 $O(n^2)$ 解决。

AC代码

源代码

心路历程（WA，TLE，MLE……）

感觉最近的 ai 属于是纯纯傻逼啊，这么简单的 bfs 都不会，非要用 dp，真的是纯纯傻逼，问题是 dp 很难解决这个问题！！！

也不能说是他们的问题。