目录
显示
题目链接
https://www.luogu.org/problem/P2886
题解
假如 \(f\) 矩阵代表走 \(x\) 条边时的最短路,\(g\) 矩阵代表走 \(y\) 条边的最短路,那么可以根据 floyd 算法,按如下规则构造 \(h\) 矩阵,代表走 \(x+y\) 条边时的最短路:
$$h_{i,j}=min\{h_{i,j},f_{i,k}+g_{k,j}\}$$
容易看出这个可以用矩阵快速幂优化计算。
#include <cstring> #include <iostream> #include <algorithm> using namespace std; struct mat { long long a[205][205]; mat(int x=0) { memset(a,x,sizeof(a)); } }f(63),ans(63); int tot,m[1005]; mat operator*(mat a,mat b) { mat c(63); for(int k=1;k<=tot;k++) for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]); return c; } int main() { int n,t,s,e; cin>>n>>t>>s>>e; for(int i=1;i<=t;i++) { int w,u,v; cin>>w>>u>>v; if(!m[u])m[u]=++tot; if(!m[v])m[v]=++tot; f.a[m[u]][m[v]]=f.a[m[v]][m[u]]=w; } for(int i=1;i<=tot;i++) ans.a[i][i]=0; while(n) { if(n&1)ans=ans*f; f=f*f; n>>=1; } cout<<ans.a[m[s]][m[e]]<<endl; return 0; }