题意:求无向图两点经过k条边的最小距离
floyd + 矩阵快速幂优化
#include <bits/stdc++.h>
using namespace std;
int num[1000005];
int n,s,t,e,tol;
struct matrix
{int a[500][500];matrix operator*(const matrix& x)const {matrix m;memset(m.a,0x3f,sizeof(m.a));for(int i=1;i<=tol;++i)for(int j=1;j<=tol;++j)for(int k=1;k<=tol;++k){m.a[i][j]=min(m.a[i][j],a[i][k]+x.a[k][j]);}return m;}
}dis,ans;
void qpow()
{n--;ans=dis;while(n){if(n&1){ans = ans * dis;}dis = dis*dis;n>>=1;}
}
int main()
{memset(dis.a,0x3f,sizeof(dis.a)); cin>>n>>t>>s>>e;while(t--){int x,y,z;cin>>z>>x>>y;if(!num[x])num[x]=++tol;if(!num[y])num[y]=++tol;dis.a[num[x]][num[y]]=dis.a[num[y]][num[x]]=z;}qpow();cout<<ans.a[num[s]][num[e]];
}