题解 P6190 【[NOI Online 入门组]魔法(民间数据)】
gaozitao1
·
·
题解
更新记录:
$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