Znzryb's Blog
0%

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

Posted on Edited on

题目大意

题目描述
给定一个包含 nn 个顶点和 mm 条边的无向图。第 ii 条边连接顶点 uiu_i 和 viv_i，其初始边权（遍历代价）为 wiw_i。

你可以将所有边的边权同时增加一个非负实数 kk。
请问：存在多少条从顶点 11 到顶点 nn 的不同路径，使得至少存在一个 kk 的值，能够让该路径成为从顶点 11 到顶点 nn 的最短路之一？

两条路径被认为是不同的，当且仅当它们包含的边数不同，或者在某一步经过了不同编号的边（即使连接的顶点相同）。
由于答案可能很大，请输出可能成为最短路的不同路径数量对 998244353998244353 取模后的结果。

输入格式
第一行包含一个整数 TT（1≤T≤10001 \le T \le 1000），表示测试用例的数量。
每个测试用例的第一行包含两个整数 nn 和 mm（2≤n≤50002 \le n \le 5000，1≤m≤50001 \le m \le 5000），分别表示图的顶点数和边数。
接下来的 mm 行，每行包含三个整数 uiu_i、viv_i 和 wiw_i（1≤ui,vi≤n1 \le u_i, v_i \le n，1≤wi≤1091 \le w_i \le 10^9），描述了一条连接 uiu_i 和 viv_i、边权为 wiw_i 的无向边。
保证所有测试用例的 nn 之和不超过 50005000，mm 之和不超过 50005000。

输出格式
对于每个测试用例，输出一个整数，表示符合条件的路径数量对 998244353998244353 取模的值。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

样例输出

1
2
3
4
3
4

样例解释
以第一个测试用例为例，图中有 33 个顶点和 44 条边。
顶点 11 和 22 之间有两条权值为 11 的平行边。
顶点 22 和 33 之间有两条权值为 11 的平行边。
无论非负实数 kk 取何值，从 11 到 33 的最短路径一定由一条连接 1,21, 2 的边和一条连接 2,32, 3 的边组成（共经过 22 条边，总权值为 2+2k2+2k）。包含边的组合情况共有 2×2=42 \times 2 = 4 种不同路径，因此答案为 44。

对于第二个测试用例：
有三条从 11 到 55 的主要路径方案：
路径一：直接走边 1↔51 \leftrightarrow 5，包含 11 条边，初始总权值为 33。当所有边权增加 kk 时，该路径的总代价为 3+k3 + k。
路径二：依次经过 1↔2↔51 \leftrightarrow 2 \leftrightarrow 5，包含 22 条边，初始总权值为 1+2=31 + 2 = 3。当所有边权增加 kk 时，该路径的总代价为 3+2k3 + 2k。
路径三：依次经过 1↔3↔4↔51 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5，包含 33 条边，初始总权值为 1+1+1=31 + 1 + 1 = 3。当所有边权增加 kk 时，该路径的总代价为 3+3k3 + 3k。
可以发现，当 k=0k=0 时，这三条路径的总代价都是 33，均能够成为从 11 到 55 的最短路。因此可能的路径总数为 33。

对于第三个测试用例，答案经过相同的逻辑推导，共有 44 条路径有可能在某个 kk 值下成为最短路。

思路讲解

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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)O(n) 的解决，也可以使用 naive 的方法 O(n2)O(n^2) 解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
AC
https://codeforces.com/gym/106139/submission/367332908

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

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

也不能说是他们的问题。

image