分析
设 $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;
}