设矩阵 \(M^1=\begin{bmatrix} dis_{1,1} & \dots & dis_{1,n}\\ \vdots & \ddots & \vdots \\ dis_{1,n} & \cdots & dis_{n,n} \end{bmatrix}\)，其中 \(dis_{i,j}\) 表示 \(i\) 是否能在 \(1\) 步内走到 \(j\)。
让我们回忆一下矩阵乘法，\(c_{i,j}=\sum_{k=1}^{n} a_{i,k}+b_{k,j}\)，这个很像我们的最短路转移。于是我们用矩乘加速，计算即可。
点击查看代码
struct node {
int x[201][201];
}awa;
int n,t,st,ed;
unordered_map<int,int>mp; int cnt;
node mul(node a,node b){
node res; mem(res.x,0x3f);
For(i,1,cnt) For(j,1,cnt) For(k,1,cnt)
res.x[i][j]=min(res.x[i][j],a.x[i][k]+b.x[k][j]);
return res;
}
node qpo(node a,int b) {
node res=a; b--;
while(b) {
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
signed main() {
in2(n,t); in2(st,ed);
mem(awa.x,0x3f);
For(i,1,t) {
int u,v,d;
in3(d,u,v);
if(!mp[u]) mp[u]=++cnt;
if(!mp[v]) mp[v]=++cnt;
awa.x[mp[u]][mp[v]]=awa.x[mp[v]][mp[u]]=min(awa.x[mp[u]][mp[v]],d);
}
// For(i,1,cnt) For(j,1,cnt) cout<<awa.x[i][j]<<(j==cnt?'\n':' ');
awa=qpo(awa,n);
cout<<awa.x[mp[st]][mp[ed]];
}