题解 P6190 【[NOI Online 入门组]魔法(民间数据)】

· · 题解

更新记录:

$2020$ 年 $3$ 月 $16$ 日完成第一版。 --- 题解可能有一点长,请耐心看完 ~~谢谢~~。 由于本人能力有限,不保证题解中的所有内容都是完全准确的。如果发现问题欢迎交流。 ~~2020 年 CCF 入门组测试出两个紫题,提高组都只是 3 个蓝题。~~\ 现在本题降蓝啦 ~~哭~~。~~不过提高组全降青啦!入门组橙紫蓝,提高组三青,还是略胜一筹的。~~ **题目大意**:有一个 $n$ 个点,$m$ 条边的图,你可以使用 $k$ 次魔法,使通过下一条道路时,距离变为原来的相反数,问从 $1$ 到 $n$ 的最小距离。 ~~前置知识:最短路,记忆化搜索,矩阵快速幂(默认大家都会qwq)。为了养成良好习惯,本题单源最短路均使用 Dijkstra。~~ 注:本题所有代码提交时均选择 C++23 且开启 O2 优化。 # 目录 1. $30$ 分--最短路(针对 $k=0$); 2. $70$ 分--记忆化搜索(暴力及其优化); 3. ~~70~~ $90$ 分--动态规划(基于全源最短路); 4. $90$ 分--动态规划(基于单源最短路)。 5. $90$ 分--分层图(基于单源最短路); 6. $100$ 分--动态规划 & 矩阵快速幂 7. $100$ 分--动态规划 & 矩阵快速幂(小优化); 8. 其他内容; 9. Hack 错误做法。 # $30$ 分--最短路(针对 $k=0$) ~~显然~~ 当 $k=0$ 时,就是一个最短路的板子题,因为 $n$ 的范围太小了,Floyd 就可以通过。 时间复杂度 $O\left(n^3\right)$,空间复杂度 $O\left(n^2\right)$。只有 $k=0$ 时能保证正确性。\ 预计得分 $30$ 分,实际得分 $30$ 分。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100; long long d[N + 1][N + 1];//d[i][j]表示从i到j的最小距离,注意开long long int main() { ios::sync_with_stdio(0); cin.tie(0); memset(d, 0x3f, sizeof(d));//0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 int i, j, k, l, m, n, u, v; cin >> n >> m >> k; for (i = 1; i <= n; ++i) d[i][i] = 0; for (i = 1; i <= m; ++i) cin >> u >> v >> d[u][v]; for (l = 1; l <= n; ++l) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) d[i][j] = min(d[i][j], d[i][l] + d[l][j]); cout << d[1][n]; return 0; } ``` :::: 当然,使用单源最短路也是可以的。下面代码给出 Dijkstra 的代码。 时间复杂度 $O\left(\left(n+m\right)\log n\right)$,空间复杂度 $O\left(n+m\right)$。只有 $k=0$ 时能保证正确性。\ 预计得分 $30$ 分,实际得分 $30$ 分。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100; int b[N + 1]; //判断点是否进入过堆 long long d[N + 1];//d[i]表示从1到i的最小距离,注意开long long vector<pair<int, int>>g[N + 1];//存图 //小根堆,第一关键字距离,第二关键词编号 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>q; inline void dijkstra() { int i, l, u, v, t; while (!q.empty()) { u = q.top().second; q.pop(); if (b[u]) continue; b[u] = 1; l = g[u].size(); for (i = 0; i < l; ++i) { v = g[u][i].first; t = g[u][i].second; if (!b[v] && d[v] > d[u] + t) { d[v] = d[u] + t; q.push({d[v], v}); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int i, k, m, n, u, v, t; cin >> n >> m >> k; for (i = 1; i <= m; ++i) { cin >> u >> v >> t; g[u].push_back({v, t}); } memset(d, 0x3f, sizeof(d));//0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 d[1] = 0; q.push({0, 1}); dijkstra(); cout << d[n]; return 0; } ``` :::: # $70$ 分--记忆化搜索(暴力及其优化) 考虑 $k\ge 0$ 的所有情况,首先能想到的就是搜索。搜索要保存的状态有三个:当前点,使用魔法次数,当前距离。每到达一个点,对这个点枚举每一条边并更新状态继续搜索。 单纯的搜索时间复杂度很夸张,需要进行优化。我们可以使用记忆化搜索的方式。 一种方法是记录到达 $i$ 点花费不超过 $j$ 次魔法时的最小距离。(正确性证明:多使用魔法后最小距离不会增加。)剪枝的过程为如果当前的距离大于记录的最小距离就跳过,否则就更新最小距离。 ~~时间复杂度分析是个人想法与评测时间结合推断,不保证正确。~~ 总共有 $nk$ 个状态( $n$ 个节点 $k$ 次魔法),每个状态下需要更新记忆数组和遍历该点连接的边,这需要 $O\left(m+k\right)$。总时间复杂度 $O\left(nk\left(m+k\right)\right)$。\ 由于要存储记忆数组,空间复杂度为 $O\left(nk\right)$。\ 综合时间复杂度、空间复杂度和本题数据范围,代码可以通过 $n\le 100,m\le 200,k\le 50$ 的所有点,且能够处理有环和无环的情况。\ 预计得分 $70$ 分,实际得分 $70$ 分。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, K = 50; int k; //搜索中要用到k,定义为全局变量 long long a[N + 1][K + 1]; //a[i][j]记录使用不超过j次魔法到达i点的最小距离,注意要开long long vector<pair<int, int>>g[N + 1];//存图 void dfs(int b, int c, long long d) //b表示当前点,c表剩余魔法次数,d表示当前距离,注意d要开long long { if (c < 0 || a[b][k - c] <= d) return;//如果不合法或有更优方案就放弃当前方案 int i, s = g[b].size(); for (i = k - c; i <= k; ++i)//更新最小距离 { if (a[b][i] <= d) break;//对于同一个点,最小距离随着使用魔法次数的增加是严格不增的,遇到第一个不超过d的就可以跳过 a[b][i] = d; } for (i = 0; i < s; ++i)//对每一条边尝试使用魔法和不使用魔法 { dfs(g[b][i].first, c - 1, d - g[b][i].second); //使用魔法 dfs(g[b][i].first, c, d + g[b][i].second); //不使用魔法 } } int main() { ios::sync_with_stdio(0); cin.tie(0); int i, m, n, t, u, v; cin >> n >> m >> k; for (i = 1; i <= m; ++i) { cin >> u >> v >> t; g[u].push_back({v, t}); } memset(a, 0x7f, sizeof(a)); //预处理为最大值 dfs(1, k, 0); cout << a[n][k]; return 0; } ``` :::: # ~~70~~ $90$ 分--动态规划(基于全源最短路) 这一道题是一个 dp 题,可以先处理使用 $0$ 次和 $1$ 次魔法的情况,之后用动态规划求出使用 $2$ 到 $k$ 次魔法的情况。 先介绍朴素的状态转移:数组 $d[k][i][j]$ 表示 $i$ 点到 $j$ 点使用至多 $k$ 次魔法的最小价值。 首先是几个状态转移方程: 1. 不使用魔法:$d[0][i][j]=\min\left(d[0][i][j],d[0][i][l]+d[0][l][j]\right)$,就是 Floyd 的转移方程。 2. 使用 $1$ 次魔法:$d[1][i][j]=\min\{d[0][i][j],d[1][i][j],d[0][i][u_l]+d[0][v_l][j]-t_l\}$。使用魔法之后距离肯定不超过不使用魔法的距离,所以第一项是 $d[0][i][j]$。此时 $l$ 就不是 Floyd 那样枚举中转点,而是枚举每一条边,看是在哪一条边使用魔法。从 $i$ 到 $u_l$ 正常走,从 $u_l$ 到 $v_l$ 使用一次魔法,距离变成 $-t_l$,从 $t_l$ 到 $j$ 也是正常走。所以状态转移方程如上。 3. 使用 $k$ 次魔法($k\ge 2$):$d[k][i][j]=\min\left(d[k][i][j],d[1][i][l]+d[k-1][l][j]\right)$。此时回到枚举中转点上来,在中转点之前使用 $k-1$ 次魔法,在中转点之后使用 $1$ 次魔法。由于 $i$ 和 $j$ 都是从 $1$ 到 $n$,所以不需要再单独计算中转点钱使用 $1$ 次在中转点后使用 $k-1$ 次魔法的情况。 这样,我们就可以求出使用 $k$ 次魔法时,任意两点之间的最小距离了。 时间复杂度 $O\left(n^2m+n^3k\right)$,空间复杂度 $O\left(n^2k\right)$。考虑优化。 当 $k\ge 2$ 时,根据状态转移方程,我们不需要保存使用所有次数的魔法时的最小距离,只需要:使用 $1$ 次魔法和使用 $k-1$ 次魔法的距离。所以状态转移不需要三维,只需要两维。 例如 $d[2][i][j]=\min\left(d[2][i][j],d[0][i][l]+d[1][l][j]\right)$。其中 $d[0],d[1],d[2]$ 分别为使用 $k-1,1,k$ 次魔法时的最小价值。 这样将空间复杂度从 $O\left(n^2k\right)$ 降到了 $O\left(n^2\right)$。 对只使用 $1$ 次魔法的情况,我们也可以使用另外一种方式:将 $d[1][i][j]$ 初始化为所有负边,之后使用状态转移方程:$d[1][i][j]=min\{d[1][i][j],d[0][i][l]+d[1][l][j],d[1][i][l]+d[0][l][j]\}$,表示取“走 $i−j$ 的负边”和“走 $i−l−j$ 并在其中一段走负边”的最小值。 这样将这一部分的时间复杂度从 $O\left(n^2m\right)$ 降到了 $O\left(n^3\right)$。 注意,这里不能像 $k\ge 2$ 时固定一段使用 $1$ 次魔法而另一段不使用魔法,因为此时 $d[1][i][j]$ 不是存储的使用一次魔法后从 $i-j$ 的最小距离,只是对这条边使用魔法的结果,与最小距离有着很大的区别。 时间复杂度为 $O\left(n^3k\right)$,空间复杂度 $O\left(n^2\right)$。 预计得分 $70$ 分,**实际得分 $90$ 分**。洛谷的评测机还是太夸张了,$200$ ms 跑 $10^9$。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, M = 2500; long long d[3][N + 1][N + 1]; //d[0][i][j],d[1][i][j],d[2][i][j]分别表示使用k-1次魔法、1次魔法和k次魔法时的最小距离 int main() { ios::sync_with_stdio(0); cin.tie(0); memset(d, 0x3f, sizeof(d)); //0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 int i, j, k, l, m, n, o, u, v; cin >> n >> m >> k; for (i = 1; i <= n; ++i) d[0][i][i] = d[1][i][i] = 0; for (i = 1; i <= m; ++i) { cin >> u >> v >> d[0][u][v]; d[1][u][v] = -d[0][u][v]; } //处理不使用魔法的情况,也就是Floyd板子 for (l = 1; l <= n; ++l) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) d[0][i][j] = min(d[0][i][j], d[0][i][l] + d[0][l][j]); if (k) { //处理使用1次魔法的情况 for (i = 1; i <= n; ++i) for (l = 1; l <= n; ++l) for (j = 1; j <= n; ++j) d[1][i][j] = min(d[1][i][j], min(d[0][i][l] + d[1][l][j], d[1][i][l] + d[0][l][j])); //存储使用1次魔法时的最小距离 memcpy(d[0], d[1], sizeof(d[0])); for (o = 2; o <= k; ++o) //枚举使用几次魔法,从2开始就可以了 { for (i = 1; i <= n; ++i) //枚举起点 for (l = 1; l <= n; ++l) //枚举转折点 for (j = 1; j <= n; ++j) //枚举终点 d[2][i][j] = min(d[2][i][j], d[0][i][l] + d[1][l][j]);//更近使用k次魔法时的最小距离 //存储使用k-1次魔法时的最小距离 memcpy(d[0], d[2], sizeof(d[0])); } } cout << d[0][1][n]; return 0; } :::: # $90$ 分--动态规划(基于单源最短路) 在上面的代码中,我们计算出了任意两点之间,使用至多 $k$ 次魔法时的最小距离。而题目只需要计算出从 $1$ 到 $n$ 使用至多 $k$ 次魔法的做小距离。所以我们可以沿用上面的状态转移思路,而使用单源最短路进行计算。下面以 Dijkstra 为例。 第一步 ~~显然~~ 是需要计算出 $1$ 到其他点的单源最短路。这部分就是最短路的板子。 之后,对于每次使用魔法,枚举每一条边 $u_i,v_i$,状态转移为 $d[k][v_i]=min\left(d[k-1][v_i],d[k-1][u_i]-t_i\right)$。这样能够找到当前情况对每条边使用魔法能否有更优方案。 但是这样还是不行的,比如从 $1$ 到 $2$ 到 $3$ 到 $n$,在 $2-3$ 使用魔法,找到了从 $1-3$ 的最短路,但是到 $n$ 的距离也会缩短。所以每次进行完一次状态转移,需要在当前的距离数组下,使用原始边再进行一次单源最短路,来更新 $1$ 到所有点的使用魔法的最短路。 这个思路也可以优化。空间上,我们只需要存使用 $k-1$ 次魔法的状态,所以可以去掉一维。时间上,我们不需要跑一遍完整的最短路。比如还是上面的例子,从 $1-2$ 的距离没变,只有经过 $2-3$ 这一条边之后的路径才会变。所以我们只需要把所有更新过的点(比如例子中的 $3$ )放入堆中进行松弛即可。 时间复杂度 $O\left(k\left(n+m\right)\log n\right)$,空间复杂度 $O\left(n+m\right)$。\ 预计得分 $90$ 分,实际得分 $90$ 分。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, M = 2500; int b[N + 1], u[M + 1], v[M + 1], t[M + 1]; long long d[2][N + 1];//d[0][i],d[1][i]分别表示使用k-1次魔法和使用k次魔法时从1到i的最小距离,注意开long long vector<pair<int, int>>g[N + 1];//vector存图 //小根堆,第一关键字距离,第二关键词编号 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>q; inline void dijkstra() { memset(b, 0, sizeof(b)); //清空标记数组 int i, l, u, v, t; while (!q.empty()) { u = q.top().second; q.pop(); if (b[u]) continue; b[u] = 1; l = g[u].size(); for (i = 0; i < l; ++i) { v = g[u][i].first; t = g[u][i].second; if (!b[v] && d[0][v] > d[0][u] + t) { d[0][v] = d[0][u] + t; q.push({d[0][v], v}); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int i, j, k, m, n; cin >> n >> m >> k; for (i = 1; i <= m; ++i) { cin >> u[i] >> v[i] >> t[i]; g[u[i]].push_back({v[i], t[i]}); } //先处理不使用魔法的情况,Dijkstra板子 memset(d[0], 0x3f, sizeof(d[0])); //0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 d[0][1] = 0; q.push({0, 1}); dijkstra(); for (j = 1; j <= k; ++j) //枚举使用魔法的次数 { //使用k次魔法的距离肯定不超过使用k-1次魔法的距离,可以用使用k-1次魔法的距离来初始化使用k次魔法的距离 memcpy(d[1], d[0], sizeof(d[1])); for (i = 1; i <= m; ++i)//尝试对每一条边使用魔法 if (d[1][v[i]] > d[0][u[i]] - t[i]) { d[1][v[i]] = d[0][u[i]] - t[i]; q.push({d[1][v[i]], v[i]}); } memcpy(d[0], d[1], sizeof(d[0])); //保存距离 dijkstra();//更新距离 } cout << d[0][n]; return 0; } ``` :::: # 90分--分层图(基于单源最短路) 这一道题也可以使用分层图的方法做。我们可以建一个 $k$ 层的图,每一层的图上的边都是正数,而相邻层之间的边是负数,这样每次使用魔法相当于往上走了一层。之后,我们只需要从 $1$ 开始,跑一次单源最短路,之后对于每一层的 $n$ 点取最小值,即为答案。 由于只有层之间的边才可能为负数,所以我们可以在每一层使用 Dijkstra,之后在从层之间的每一条边走上去,之后继续使用 Dijkstra。为了实现这一过程,可以在堆中添加一个变量作为层数,以层数为第一关键字,距离为第二关键字。~~费劲做这么多就是怕出题人卡 SPFA。~~ 点的量级为 $nk$,边的量级为 $mk$,时间复杂度 $O\left(k\left(n+m\right)\log \left(kn\right)\right)$。空间复杂度 $O\left(k\left(n+m\right)\right)$。\ 预计得分 $90$ 分。实际得分 $90$ 分。~~由于常数过大,这个方法的用时和基于全源最短路的动态规划几乎相同。~~ ~~这种思路其实和上面基于单源最短路的动态规划是一样的,而时间复杂度与空间复杂度都不如上面的方法。但是由于这部分是我第一次题解中包含的,我还是保存了下来。~~ ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, M = 2500, K = 1000; int b[K + 1][N + 1]; long long d[K + 1][N + 1]; //d[k][i]表示1点到k层的i号点的最短距离 struct node { int a, v, t; //依次表示层数,点编号,距离 }; vector<node>g[K + 1][N + 1]; //vector存图 //小根堆,第一关键字层数,第二关键字距离 struct Node { int a;//层数 long long b;//距离 int u;//点 bool operator<(const Node& c) const { return a == c.a ? b > c.b : a > c.a; } }; priority_queue<Node>q; inline void dijkstra() { int a, A, i, l, u, v, t; while (!q.empty()) { a = q.top().a;//需要额外记录层数 u = q.top().u; q.pop(); if (b[a][u]) continue; b[a][u] = 1; l = g[a][u].size(); for (i = 0; i < l; ++i) { A = g[a][u][i].a; v = g[a][u][i].v; t = g[a][u][i].t; if (!b[A][v] && d[A][v] > d[a][u] + t) { d[A][v] = d[a][u] + t; q.push({A, d[A][v], v}); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int i, j, k, m, n, t, u, v; long long a; cin >> n >> m >> k; for (i = 1; i <= m; ++i) { cin >> u >> v >> t; g[0][u].push_back({0, v, t}); //第0层的边 for (j = 1; j <= k; ++j) { g[j - 1][u].push_back({j, v, -t}); //j-1层和j层之间的边 g[j][u].push_back({j, v, t}); //第j层的边 } } memset(d, 0x3f, sizeof(d)); //0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 d[0][1] = 0; q.push({0, 0, 1}); dijkstra(); a = d[0][n]; for (i = 1; i <= k; ++i)//最后结果是每一层的n点的最小值 a = min(a, d[i][n]); cout << a; return 0; } ``` :::: # $100$ 分--动态规划 & 矩阵快速幂 观察基于全源最短路的动态规划 $1$ 中的状态转移方程: $d[2][i][j] = \min\left(d[2][i][j], d[0][i][l] + d[1][l][j]\right)$。 会发现这个方程非常像矩[阵乘法的方程: $d[i][j]=d[i][j]+d[i][l]\times d[l][j]$。 如果把 $+$ 换成 $\times$,把 $\min$ 换成“求和”,那么就是矩阵乘法了。 而这个转移方程,其实也有专属的名字:**Min-plus**。 结合状态转移方程与 Min-plus,我们可以得到:第 $k$ 次使用魔法的距离,等于第 $k-1$ 次魔法的距离与第 $1$ 次使用魔法的距离进行 Min-plus。这样,我们可以使用类似矩阵快速幂的方法进行加速。 而且,构造只使用一次魔法的矩阵时的状态转移,其实就是两个 Min-plus。也可以简化一下代码。 主要思路与动态规划相似,先求出使用 $0$ 次和 $1$ 次魔法的结果,之后计算使用 $1$ 次魔法的矩阵在 Min-plus 下的 “$k$ 次幂”即可。 时间复杂度 $O\left(n^3\log k\right)$,空间复杂度 $O\left(n^2\right)$。\ 预计得分 $100$ 分,实际得分 $100$ 分。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, M = 2500; struct Matrix { int n; long long d[N + 1][N + 1]; //使用魔法后的最小距离 Matrix operator*(const Matrix& a) const//实际上是Min-plus { int i, j, k; Matrix b = a; for (i = 1; i <= n; ++i) for (k = 1; k <= n; ++k) for (j = 1; j <= n; ++j) b.d[i][j] = min(b.d[i][j], d[i][k] + a.d[k][j]); return b; } } a, b, d; int main() { ios::sync_with_stdio(0); cin.tie(0); memset(a.d, 0x3f, sizeof(a.d)); //0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 memset(d.d, 0x3f, sizeof(d.d)); int i, j, k, l, m, n, u, v; cin >> n >> m >> k; a.n = d.n = n; for (i = 1; i <= n; ++i) a.d[i][i] = d.d[i][i] = 0; for (i = 1; i <= m; ++i) { cin >> u >> v >> d.d[u][v]; a.d[u][v] = -d.d[u][v]; } //处理不使用魔法的情况,也就是Floyd板子 for (l = 1; l <= n; ++l) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) d.d[i][j] = min(d.d[i][j], d.d[i][l] + d.d[l][j]); if (k) { a = d * a * d;//处理使用1次魔法的情况,使用Min-plus简化代码 b = a; for (--k; k; k >>= 1) { if (k & 1) a = a * b; b = b * b; } cout << a.d[1][n]; } else cout << d.d[1][n]; return 0; } ``` :::: # $100$ 分--动态规划 & 矩阵快速幂(小优化) 上面的做法也可以进行小 ~~卡常~~ 优化。 基于动态规划的两个方法的区别,我们自然可以想到只计算从 $1$ 到其他所有点的最短路。用 $a$ 表示使用 $1$ 次魔法的 $n\times n$ 的矩阵,那么在刚刚的计算中,我们计算了 $a^k$。而我们实际上只需要计算从 $1$ 到 $n$ 的最短路程,所以我们可以使用 $1\times n$ 的 $b$ 矩阵记录使用一次魔法后从 $1$ 到其他点的最短路程,之后计算 $b\times a^{k-1}$ 即可。这样在矩阵快速幂的部分计算中,我们从计算 $n\times n$ 的矩阵乘 $n\times n$ 的矩阵,变为计算 $1\times n$ 的矩阵乘 $n\times n$ 的矩阵,能够简化许多运算。 时间复杂度 $O\left(n^3\log k\right)$,空间复杂度 $O\left(n^2\right)$。\ 预计得分 $100$ 分,实际得分 $100$ 分。\ 本代码所有测试点用时均不超过 $10$ ms。 ::::info[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100, M = 2500; struct Matrix { int n, m; //n行m列 long long d[N + 1][N + 1]; //使用魔法后的最小距离 Matrix operator*(const Matrix& a) const//实际上是Min-plus { int i, j, k; Matrix b; b.n = n; b.m = a.m; memset(b.d, 0x3f, sizeof(b.d)); for (i = 1; i <= n; ++i) for (k = 1; k <= m; ++k) for (j = 1; j <= a.m; ++j) b.d[i][j] = min(b.d[i][j], d[i][k] + a.d[k][j]); return b; } } a, b, d; int main() { ios::sync_with_stdio(0); cin.tie(0); memset(a.d, 0x3f, sizeof(a.d)); //0x3f约为4.56*10^18,两倍不会超过long long范围,且大于本题可能的距离最大值 memset(d.d, 0x3f, sizeof(d.d)); int i, j, k, l, m, n, u, v; cin >> n >> m >> k; a.n = a.m = d.n = d.m = n; for (i = 1; i <= n; ++i) a.d[i][i] = d.d[i][i] = 0; for (i = 1; i <= m; ++i) { cin >> u >> v >> d.d[u][v]; a.d[u][v] = -d.d[u][v]; } //处理不使用魔法的情况,也就是Floyd板子 for (l = 1; l <= n; ++l) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) d.d[i][j] = min(d.d[i][j], d.d[i][l] + d.d[l][j]); if (k) { a = d * a * d;//处理使用1次魔法的情况,使用Min-plus简化代码 b = a; a.n = 1;//只需保留第一行 for (--k; k; k >>= 1) { if (k & 1) a = a * b; b = b * b; } cout << a.d[1][n]; } else cout << d.d[1][n]; return 0; } ``` :::: # 其他内容 这里我对做这道题容易遇到的问题进行汇总和解答。 1. 最多 $k$ 次魔法,理想状态下每条边都是 $t_{max}$ 且都能使用魔法,最小距离为 $-kt_{max}$,超过了 $int$ 的范围。注意开 long long。 2. 数组要初始化成无穷大。如果最大值不够大,又存在负边,可能会出现无穷大被不断减小最后比答案还小的情况导致错误。解决方法主要有以下两种:松弛时判断是否为无穷大;将无穷大设置的很大。本题解中采用后面的方案。 3. 我 ~~太菜了~~ 没有想到无环的性质是给什么做法过的,所以题解中没有针对这一性质的做法。~~总不能是找到唯一路径贪心使用魔法吧。~~ 而且不清楚此性质对正解有什么关系。 4. Min-plus的初始矩阵与矩阵乘法不同,要设置成对角线为 $0$ 其他值为正无穷。 5. 有些做法是尝试寻找周期性,认为使用魔法后是在某一个相同的环上一直走。但是这种方式不保证能通过本题!~~虽然数据没有卡。~~ 下面介绍如何对这个思路进行 Hack。 # Hack 错误做法 本题有一个看起来非常正确 ~~而且卡起来有难度~~ 的做法。大体思路是认为:当魔法次数多的时候,最短路程一直是沿着相同的路(或者说环)一直转圈,并且在固定的道路使用魔法,以此思路寻找到这样一个循环并直接计算最终结果,从而完全将时间复杂度的 $k$ 给降低甚至去除。 想要卡这个思路,首先想到的是彻底消除这样一个循环。但是当 $k$ 足够大的时候,肯定会出现这样一个循环。~~(看起来很显然,我不会证,但是找不到反例)。~~ 上面的思路不行,我们就改变策略,让出现这个循环的时间往后延,当使用魔法的次数极大(超过 $10^6$)的时候,才会出现循环,导致寻找循环的过程中就会超时。 本着这个思路,可以构造出下面这样的数据 **(由于数据范围小,下面的代码可能会让“非矩阵快速幂的动态规划”通过。如果完全只想让正解通过,只需要扩大 $n$ 和 $m$ 的范围即可,思路相同)**: ::::info[输入] ``` 14 16 1000000 1 2 1 2 14 1 1 7 1 7 14 1 2 3 999999 3 4 999999 4 5 999999 5 6 999999 6 2 999999 7 8 1000000 8 9 1000000 9 10 1000000 10 11 1000000 11 12 1000000 12 13 1000000 13 7 1000000 ``` :::: ::::info[输出] ``` -999999000000 ``` :::: 这个图很简单,从 $1$ 到 $14$ 主要有两条路:$1-2-14$ 和 $1-7-14$。同时 $2$ 点在一个 $5$ 个点组成的环中(简称五环),边权均为 $999999$。$7$ 点在一个 $7$ 个点组成的环中(简称七环),边权均为 $1000000$。主路上的边权很小,环上的边权很大,而且两个环的点数互质,两个环的边权相差很小。 先考虑简单的情况。当年使用魔法的次数 $k$ 是 $35$ 的倍数的时候,有两种方案:走五环和走七环。走五环走七圈使用 $35$ 次魔法和走七环走五圈使用 $35$ 次魔法,结果相差 $35$,这样当使用 $k$ 次魔法时,走七环比走五环要少走 $k$。 但是如果使用魔法的次数不是 $35$ 的倍数,会产生零头,不能对环上的所有边都使用魔法。比如 $k=25$ 时,走五环能够保证每个边都使用魔法,但走七环会剩下许多边无法使用魔法。因为边权远大于 $35$,所以当使用魔法次数很小的时候,这种剩余边无法使用魔法的情况是无法接受的。只有当使用魔法的次数足够多,转了好多圈之后省下来的距离能够弥补剩余边的距离的时候,才会出现循环。 当 $k$ 从 $0$ 开始慢慢增大时,会有时走五环,有时走七环,有时都要走,而且没有明显的循环规律。 当 $k$ 足够大时,$k$ 的量级比边权要大一些的时候,就可以无脑走七环了,此时前面少的 $k$ 就能弥补不使用魔法的边的距离。此时就有了长度为 $7$ 的循环节。(相差 $7$ 就少走一圈) 经过 ~~严谨的数学证明~~ 粗糙的打表之后,发现当 $k\ge 3000000$ 时,一定可以无脑走七环。当 $k\le 2900000$ 时,要根据使用魔法的情况进行分析,且没有明显循环。这对于本题已经足够。~~至于具体什么时候开始出现循环,我没找到。~~ ### 完结撒花 orz