k短路 $ O(n^3logk) $
- $ 定义d_{k,i,j} 为经过了k条边的i到j的最短路 $
- $ 转移方程：d_{a+b,i,j}=min(d_{a,i,k}+d_{b,k,j}) $
- 暴力转移时间复杂度：$ O(k^2n^3) $
- 考虑倍增与快速幂的思想，将
k分离成$ 2^0+2^1... $ - 只不过此时快速幂的两数相乘，变成两个数组跑floyd
- 时间复杂度: $ O(n^3logk) $
cpp
int n,m,k,S,E;
int adj[N][N],tmp[N][N],res[N][N];
void mul(int c[][N],int a[][N],int b[][N]){
memset(tmp,0x3f,sizeof tmp);
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
}
}
memcpy(c,tmp,sizeof tmp);
}
void qpow(){
memset(res,0x3f,sizeof res);
for(int i=1;i<=n;i++)res[i][i]=0;
for(;k;k>>=1){
if(k&1)mul(res,res,adj);
mul(adj,adj,adj);
}
}
void solve(){
cin>>k>>m>>S>>E;
memset(adj,0x3f,sizeof adj);
map<int,int> ids;
if(!ids.count(S))ids[S]=++n;
if(!ids.count(E))ids[E]=++n;
S=ids[S],E=ids[E];
while(m--){
int u,v,w;
cin>>w>>u>>v;
if(!ids.count(u))ids[u]=++n;
if(!ids.count(v))ids[v]=++n;
u=ids[u],v=ids[v];
adj[u][v]=adj[v][u]=min(adj[u][v],w);
}
qpow();
cout<<res[S][E]<<"\n";
}