题解 P6190 【[NOI Online 入门组]魔法（民间数据）】
mulberror
2020-03-09 22:15:27
这题其实考察了一个小$\mathrm {trick}$。
这个$\mathrm {trick}$我第一次见到是在做 IOI2020 国家集训队作业的时候看到的，题号是[Codeforces 576D](http://blog.chhokmah.cn/index.php/archives/29/)
> 对于一个邻接矩阵$G$，那么$G^k$表示的就是**恰好**经过$k$后的状态。
举一个比较简单的例子：
$G$是一个简单的$01$邻接矩阵，$G(i,j)$表示的就是在一步内$i\rightarrow j$的方案数，$0$即意味着两者之间没有连边，也意味着$1$步内有$0$种到达的方案，$1$也同理。然后再在这个邻接矩阵做$k$遍矩阵乘法后，得到的$G'$中$(i,j)$就是在**恰好**走了$k$步，从$i\rightarrow j$的方案数。
**这个其实就代替了做动态规划的必要**
因为这$k$步，每一步的本质相同，只是对应的状态不同，所以我们考虑重载矩阵乘法的定义，了解过动态 DP 的读者也可以类比动态 DP。
对应到这道题，我们首先计算出一步能够得到的状态，然后用相同的转移来做矩阵快速幂即可。
时间复杂度 $O(n^3Log_2 k)$
```cpp
#define int long long
const int N = 105;
const int M = 2505;
int n, m, kk;
struct Matrix {
int a[N][N];
int* operator[](int i) {
return a[i];
}
Matrix operator*(Matrix oth) {
Matrix res;
memset(res.a, 0x3f, sizeof res.a);
For (k, 0, n - 1) {
For (i, 0, n - 1) {
For (j, 0, n - 1) {
chkmin(res[i][j], a[i][k] + oth[k][j]);
}
}
}
return res;
}
friend Matrix operator^(Matrix x, int idx) {
Matrix res = x;
idx--;
for (; idx; idx >>= 1, x = x * x) {
if (idx & 1) {
res = res * x;
}
}
return res;
}
};
struct Path {
int u, v, t;
} path[M];
int g[N][N];
signed main() {
memset(g, 0x3f, sizeof g);
read(n), read(m), read(kk);
For (i, 0, m - 1) {
read(path[i].u), read(path[i].v), read(path[i].t);
path[i].u--, path[i].v--;
g[path[i].u][path[i].v] = path[i].t;
}
For (i, 0, n - 1) {
g[i][i] = 0;
}
For (k, 0, n - 1) {
For (i, 0, n - 1) {
For (j, 0, n - 1) {
chkmin(g[i][j], g[i][k] + g[k][j]);
}
}
}
Matrix base;
memset(base.a, 0x3f, sizeof base.a);
For (i, 0, n - 1) {
base[i][i] = 0;
}
For (i, 0, m - 1) {
int u = path[i].u, v = path[i].v, t = path[i].t;
For (j, 0, n - 1) {
For (k, 0, n - 1) {
chkmin(base[j][k], g[j][u] - t + g[v][k]);
}
}
}
if (kk) {
writeln((base ^ kk)[0][n - 1]);
} else {
writeln(g[0][n - 1]);
}
return 0;
}
```