题解:ABC445F Exactly K Steps 2

题解:ABC445F Exactly K Steps 2

前置

第一次打如此高的分数，震惊震惊震惊。

思路

设矩阵 \(M_{i,j}^k\) 表示从 \(i\) 点出发，经过 \(k\) 条边，到达 \(j\) 点的最小路径。显然易见， \(M^1=C\) ，而对于 \(M^t\) 和 \(M^{t+1}\) ，有 \(M_{i,j}^{t+1}=\displaystyle\min_{1\le k\le n}M_{i,j}^t,M_{i,k}^t+M_{k,j}^t\) ,那么，我们只要算到 \(M^k\) 就行了，但 \(k \le 10^9\) ,我们需要快速幂。

代码

ll n, k;
vector<vector<ll>> mul(vector<vector<ll>>a,vector<vector<ll>>b){vector<vector<ll>> c(n, vector<ll>(n,Inf));for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<n;k++){c[i][j]=min(c[i][j],a[i][k]+b[k][j]);}}}return c;
}
int main(){cin>>n>>k;vector<vector<ll>> c(n, vector<ll>(n)), res(n, vector<ll>(n, Inf));for(int i=0;i<n;i++){res[i][i]=0;for(int j=0;j<n;j++){cin>>c[i][j];}}while(k){if(k&1)res=mul(res, c);c=mul(c, c);k>>=1;}for(int i=0;i<n;i++){cout<<res[i][i]<<'\n';}
}

本文来自 NoiPLE ，转载请注明原文链接：https://www.cnblogs.com/noiple-dequeee/p/19618378