题意非常简单，就是在最短路的基础的上加上了可以施魔法（经过这条边的时候，将权值取反，注意只是经过的时候取反，并不是永久的）的操作。
看到n的范围只有100，很快的就能想到floyd或者分层图
首先我们分析，每次使用魔法必然能让最短路变短，那么我们一定会将k次魔法用满，那么题意就转化为，恰好使用k次魔法的1到n的最短路。
在 acwing - 牛站这道题的时候我们知道，类floyd + 矩阵快速幂是可以logn时间内处理出点对间正好经过k条边的最小距离。
之后我最初的想法是存一个负权矩阵，之后跑floyd，这样相当于是知道点对间用了k次魔法的最短距离，之后将这些距离当作边加入原图，之后跑分层dij (分为使用了负权边与没使用) 。
跑出样例之后，提交...果不其然0分。（跑出样例的原因好像是因为我都加了双向边，当时没看到是有向边。
在看了题解之后，我才明白我错在哪里。首先存一个负权矩阵去跑floyd，这一步就不是很对。
让我们考虑一下，类floyd到底在做什么事情——类floyd在处理点对间正好经过k条边的最小距离
那么如果我们存一个负矩阵去跑的话，处理出来的是正好经过k条边的最短距离。但是题目求的是正好经过k条边么，不是的它求的是用了k次魔法的最短距离
也就是说这个使用魔法可以是不连续的，就拿题目中的样例
2 2 2 1 2 10 2 1 1 来说明。 最佳的路线是1 - 2 使用一次魔法，这样当前权值是-10，之后2 - 1不使用魔法，当前权值是-9，之后又通过1 - 2 使用魔法。最终最短距离为-19。
但是如果我们只丢一个负权矩阵去跑floyd的话，只能得到连续经过k条负权边的最小权值，于是就得不到题目中的样例。
其实这个更像是一个dp方程，我们通过矩阵快速幂去加速这个过程而已。
首先我们定义 dp[k][i][j]为使用了k 次魔法，i 到 j 的最小值。
之后我们发现dp[k][i][j] 可以从所有的dp[k - s][ i ][ t ] + dp[ s ][ t ][ j ]转移过来 ，这个过程与floyd非常相似，于是我们就想到用类floyd的办法去加速这个过程。
于是我们需要得到使用一次魔法的邻接矩阵，之后对着这个矩阵跑矩阵快速幂，最后就是答案了。
本质上是一个dp。
注意特判无法使用魔法的情况。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; ///1061109567 const int N = 100 + 10; int n, m, K, u[2500+1], v[2500+1]; ll f[N][N], g[N][N], t[N][N]; ll w[2500+1]; void mul(ll c[][N], ll a[][N], ll b[][N]) { memset(t, 0x3f, sizeof t); for (int k = 1; k <= n; ++ k) for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) t[i][j] = min(t[i][j], a[i][k] + b[k][j]); memcpy(c, t, sizeof t); } void qmi() { memset(f, 0x3f, sizeof f); for (int i = 1; i <= n; ++ i) f[i][i] = 0; while (K) { if (K & 1) mul(f, f, g); mul(g, g, g); K /= 2; } } void print2(ll p[][N]) { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { printf("%lld ", p[i][j]); } puts(""); } } int main() { scanf("%d%d%d", &n, &m, &K); memset(f, 0x3f, sizeof f); for (int i = 1; i <= n; ++ i) f[i][i] = 0; for (int i = 1; i <= m; ++ i) { scanf("%d%d%lld", &u[i], &v[i], &w[i]); f[u[i]][v[i]] = w[i]; } for (int k = 1; k <= n; ++ k) for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); if (K) { for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) t[i][j] = f[i][j]; // print2(t); for (int k = 1; k <= m; ++ k) for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) t[i][j] = min(t[i][j], f[i][u[k]] + f[v[k]][j] - w[k]); memcpy(g, t, sizeof t); // print2(g); qmi(); } printf("%lld ", f[1][n]); return 0; }