5/26
该说不说图论真是挺神奇的啊哈哈哈哈哈哈哈
P2886 [USACO07NOV] Cow Relays G
作为一个图论初学者，更不会这道题了啊哈哈哈哈
看到这个题，对于这么庞大的数据范围，心态搞炸了啊哈哈哈哈
窝草
哦，好像也不大，注意到T是边，所以考虑Floyd
但是又注意到N极大，所以又不会了。
还是这个题还是好题
首先我们想出来的是，这个题需要用到邻接矩阵？？？
哦，点很小其实也很正常。
那就会做了。
结合前面的Floyd。
转移式子是\(F_{i,j}=min(F_{i,j},F_{i,k}+F_{k,j})\)
但是题解好像说的不是很详细，都是直接跳到矩阵。
具体地说，我们为什么要使用邻接矩阵呢？
那肯定是与矩阵有关。
对于矩阵乘法，它的式子是酱紫的：
\[C_{i,j}=\sum{A_{i,k}+B_{k,j}}
\]
这个东西很像Floyd的转移对吧，但是好像我们不需要∑，我们需要的是min！
这玩意儿是图论对吧，又不是数学,我们考虑定义一个新的计算方法
\[C_{i,j}=min(A_{i,k}+B_{k,j})
\]
简而言之：
\(A_{i,k}\)表示i走到k的最短路，\(B_{k,j}\)表示k到j的最短路，\(C_{i,j}\)表示i到j的最短路
问题是我们为什么要这么做，当然是为了优化啊！
我们发现，这个题让我们经过的边十分的多，在边的数量很多的时候，我们最短路一定会走重复的边。
这些边我们可以直接一次性算出来。
再不理解，就可以理解成倍增求Floyd行了///
这样的话矩阵快速幂就很快了。
当然还有一个优化就是，我们发现有一些点是没用的，直接离散化就行了。代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T,s,e;
const int xx=1e3+5;
const int inf=1e12+18;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*f;
}
int t[xx][xx],ans[xx][xx];
int id[xx],tol;
void mul_st(int a[][xx],int b[][xx],int res[][xx]){for(int i=1;i<=tol;i++)for(int j=1;j<=tol;j++){t[i][j]=inf;}for(int k=1;k<=tol;k++)for(int i=1;i<=tol;i++)for(int j=1;j<=tol;j++)t[i][j]=min(t[i][j],a[i][k]+b[k][j]);for (int i=1;i<=tol;i++)for (int j=1;j<=tol;j++)res[i][j]=t[i][j];
}
int G[xx][xx];
void ksm(int k){for(int i=1;i<=tol;i++){for(int j=1;j<=tol;j++){ans[i][j]=G[i][j];}}k--;while(k){if(k&1) mul_st(ans,G,ans);mul_st(G,G,G);k>>=1;}
}
int get(int x) {if (!id[x]) id[x]=++tol;return id[x];
}
signed main(){n=read(),T=read(),s=read(),e=read();for(int i=1;i<=1000;i++){for(int j=1;j<=1000;j++){G[i][j]=inf;}}for(int i=1;i<=T;i++){int w=read(),u=read(),v=read();u=get(u),v=get(v);G[u][v]=G[v][u]=w;}ksm(n);cout<<ans[get(s)][get(e)]<<"\n";return 0;
}