http://47.95.147.191/problem/P3
规定边数的最短路，跑floyd+矩阵快速幂

#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cmath>#include<ctime>#include<set>#include<map>#include<stack>#include<cstring>#define inf 2147483647#define For(i,a,b) for(long long i=a;i<=b;i++)#define p(a) putchar(a)#define g() getchar()#define mod 1000000007//by war//2020.2.26using namespace std;long long n,k,S,T,x,y,lim,c;long long m[1010];struct matrix{ long long a[310][310]; matrix operator*(const matrix&b)const{ matrix r; For(i,1,n) For(j,1,n){ r.a[i][j]=inf; For(k,1,n) r.a[i][j]=min(r.a[i][j],a[i][k]+b.a[k][j]); } return r; }}a;void in(long long &x){ long long y=1; char c=g();x=0; while(c<‘0‘||c>‘9‘) { if(c==‘-‘) y=-1; c=g(); } while(c<=‘9‘&&c>=‘0‘)x=(x<<1)+(x<<3)+c-‘0‘,c=g(); x*=y;}void o(long long x){ if(x<0) { p(‘-‘); x=-x; } if(x>9)o(x/10); p(x%10+‘0‘);}matrix ksm(matrix a,long long b){ matrix r=a;b--; while(b>0){ if(b%2==1) r=r*a; a=a*a; b>>=1; } return r;}int main(){ in(lim);in(k);in(S);in(T); For(i,0,300) For(j,0,300) a.a[i][j]=inf; For(i,1,k){ in(c);in(x);in(y); if(!m[x]) m[x]=++n; if(!m[y]) m[y]=++n; a.a[m[x]][m[y]]=a.a[m[y]][m[x]]=c; } matrix r=ksm(a,lim); o(r.a[m[S]][m[T]]); return 0;}