全网都是矩阵快速幂，我只会倍增DP

其实这题与 AcWing 345. 牛站 还是比较像的，那题可以矩阵快速幂 / 倍增，这题也行。

先 $Floyd$ 预处理两点之间不用魔法最短距离 $d_{i, j}$ 复杂度 $O(n^3)$

然后预处理两点之间至多用一个魔法的最短距离 $w_{i, j}$，初始为 $w_{i, j} = d_{i, j}$，枚举 $i, j$ 和一条边 $(u, v, t)$ $w_{i, j} = \min(d[i][u] - t + d[v][j])$，复杂度 $O(n^2m)$

然后把 $w$ 数组当做邻接矩阵的新图，所以问题变成了走恰好 $k$ 条边的最短路（可以理解多走不会变差，因为满足 $w_{i, i} <= 0$），这个问题就是 AcWing 345. 牛站 ，具体做法看 AcWing 345. 牛站的倍增 DP 思路，复杂度 $O(n^3 \log K)$

注意细节，走 $0$ 条边的最短路是 $d_{1, n}$，注意 $f$ 的初始值。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 105, M = 2505, L = 20;
const LL INF = 1e18;

int n, m, K, l;
LL d[N][N], w[N][N], g[L][N][N], f[N], t[N];

struct E{
    int u, v, w;
} e[M];

int main() {
    memset(g, 0x3f, sizeof g);
    scanf("%d%d%d", &n, &m, &K);
    l = log2(K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) d[i][j] = INF;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        d[e[i].u][e[i].v] = min(d[e[i].u][e[i].v], (LL)e[i].w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i][j] = d[i][j];
            for (int k = 1; k <= m; k++)
                w[i][j] = min(w[i][j], d[i][e[k].u] - e[k].w + d[e[k].v][j]);
            g[0][i][j] = w[i][j];
        }
    }
    for (int c = 1; c <= l; c++) 
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                for (int k = 1; k <= n; k++) 
                    g[c][i][j] = min(g[c][i][j], g[c - 1][i][k] + g[c - 1][k][j]);
    for (int i = 1; i <= n; i++) f[i] = d[1][i];
    for (int c = 0; c <= l; c++) {
        if (K >> c & 1) {
            for (int i = 1; i <= n; i++) t[i] = f[i];
            memset(f, 0x3f, sizeof f);
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= n; j++) f[i] = min(f[i], t[j] + g[c][j][i]);
        }
    }
    printf("%lld\n", f[n]);
    return 0;
}