Luogu

分析

设 $dp_{i,j,k}$ 表示用了 $k$ 次魔法从 $i$ 走到 $j$ 的最小费用。显然有转移

$$ dp_{i,j,k}=\min_{p=1}^n\left\{dp_{i,p,k-1}+dp_{p,j,1}\right\} $$

足够熟练的话可以看出是一个广义矩阵乘法（将 $+$ 改为 $\min$，将 $\times$ 改为 $+$，仍然满足结合律）的形式，预处理 $dp_{i,j,1}$ 后矩阵快速幂即可。

预处理 $dp_{i,j,1}$ 可以先 Floyd 预处理出两两之间的最短路，然后枚举哪条边取负。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,M=2500+10;

int n,m,k;
int x[M],y[M],z[M];
ll dis[N][N];

struct Matrix {
    ll s[N][N];
    Matrix() { memset(s,0x3f,sizeof(s)); }
    ll* operator [](int i) { return s[i]; }
} Q;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=1;i<=n;++i)
        for (int k=1;k<=n;++k)
            for (int j=1;j<=n;++j)
                c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
    return c;
}
Matrix qpow(Matrix a,int b) {
    Matrix c=a;
    for (--b;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),m=read(),k=read();
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=m;++i) {
        x[i]=read(),y[i]=read(),z[i]=read();
        dis[x[i]][y[i]]=z[i];
    }
    for (int i=1;i<=n;++i) dis[i][i]=0;
    for (int k=1;k<=n;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    if (!k) { printf("%lld\n",dis[1][n]); return 0; }
    for (int i=1;i<=n;++i) Q[i][i]=0;
    for (int k=1;k<=m;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                Q[i][j]=min(Q[i][j],dis[i][x[k]]-z[k]+dis[y[k]][j]);
    Q=qpow(Q,k);
    printf("%lld\n",Q[1][n]);
    return 0;
}