题目链接
description
给定一张简单带权有向图以及一个非负整数 \(k\)，从 1 号节点出发，最终到 \(n\) 号节点，可重复经过点，且可以不超过 \(k\) 次将当前经过的边的权值变为它的相反数计入花费（只改变一次花费，而非改变边权）。求最小费用。
\(n\leq 100\) (点数)
\(m\leq 2500\) (边数)
\(k\leq 10^6\)
solution
\(k\leq 50\) 的点直接分层图spfa就可以了，但是难以扩展到 \(k\leq 10^6\) 的情况。
考虑dp做法。
\(f_{t,i,j}\) 表示改变不超过 \(t\) 次权值，从节点 \(i\) 到 \(j\) 的最小花费。
考虑如何转移。
一段改变了不超过 \(t\) 次权值的路径可以分成两段：
-
从起点到路径上某个点，改变不超过 \(t-1\) 次权值的路径
-
从该点到终点改变不超过 1 次权值的路径
类比floyd枚举中转点即可，由此可知 \(f_{t,i,j}=\min\limits_{1\leq k\leq n} \{f_{t-1,i,k}+f_{1,k,j}\}\)
我们还需要求出 \(f_1\)。
先做一遍 floyd 求出 \(f_0\)，求出全源最短路。对于每组 \((i,j)\)，因为边数不多，我们可以枚举边，所以有 \(f_{1,i,j}=\min\limits_{(a,b)\in E}\{f_{0,i,a}-w(a,b)+f_{0,b,j}\}\)。
然后dp，时间复杂度 \(\mathcal{O}(n^2m+kn^3)\)，会 t 飞。
考虑优化。
因为 \(f_{t,i,j}=\min\limits_{1\leq k\leq n} \{f_{t-1,i,k}+f_{1,k,j}\}\)
所以可以把 \(f_t\)， \(f_{t-1}\)， \(f_1\) 视作矩阵，
那么 \(f_t=f_{t-1}\times f_1\)，其中的矩阵乘法是 \((\min,+)\)。
于是我们只需矩阵快速幂求出 \(f_k=(f_1)^k\) 即可。
时间复杂度 \(\mathcal{O}(n^2m+n^3\log k)\)。
code
#include<bits/stdc++.h>
//代码应该比较明白了，就不写注释了qwq
using namespace std;
template<typename T>
void read(T &x){
x=0;
int sgn=0;
char c=getchar();
while(!isdigit(c)) sgn|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10-'0'+c,c=getchar();
if(sgn) x=-x;
}
const int N=110,M=2510;
int n,m,k;
long long w[N][N];
struct Matrix{
int _n,_m;
long long _[N][N];
void prin(){
cerr<<endl<<"DEBUG"<<endl;
for(int i=1; i<=_n; i++){
for(int j=1; j<=_m; j++){
cerr<<_[i][j]<<' ';
}
cerr<<endl;
}
cerr<<endl;
}
friend Matrix operator*(const Matrix &x,const Matrix &y){
Matrix z;
z._n=x._n,z._m=y._m;
memset(z._,0x3f,sizeof z._);
for(int i=1; i<=z._n; i++) z._[i][i]=0;
for(int i=1; i<=z._n; i++){
for(int k=1; k<=x._m; k++){
for(int j=1; j<=z._m; j++){
z._[i][j]=min(z._[i][j],x._[i][k]+y._[k][j]);
}
}
}
return z;
}
};
vector<pair<int,int>> edge;
inline Matrix qpow(Matrix a,int b){
Matrix ret;
memset(ret._,0x3f,sizeof ret);
ret._n=ret._m=a._n;
for(int i=1; i<=a._n; i++) ret._[i][i]=0;
while(b){
if(b&1) ret=ret*a;
a=a*a;
b>>=1;
}
return ret;
}
int main(){
read(n),read(m),read(k);
memset(w,0x3f,sizeof w);
for(int i=1; i<=m; i++){
int x,y,z;
read(x),read(y),read(z);
w[x][y]=z;
edge.push_back({x,y});
}
for(int i=1; i<=n; i++) w[i][i]=0;
Matrix A0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
A0._[i][j]=w[i][j];
if(i==j) A0._[i][j]=0;
}
}
A0._n=A0._m=n;
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
A0._[i][j]=min(A0._[i][k]+A0._[k][j],A0._[i][j]);
}
}
}
if(k==0){ //记得特别处理一下k=0的情况
//原因是 f_0!=(f_1)^0
printf("%lld\n",A0._[1][n]);
return 0;
}
Matrix A1=A0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(auto p:edge){
A1._[i][j]=min(A1._[i][j],A0._[i][p.first]+A0._[p.second][j]-w[p.first][p.second]);
}
}
}
auto res=qpow(A1,k);
/*
res.prin();
A1.prin();
A0.prin();
*/
printf("%lld\n",res._[1][n]);
return 0;
}