倍增 $ Floyd $

注意结构体里二维数组不能开到 $ 2000 $

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define Re register using namespace std;inline int read(){    char ch = getchar();    int f = 1 , x = 0;    while(ch > '9' || ch < '0') {if(ch == '-' ) f = -1 ; ch = getchar();}    while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar();}    return x * f;}long long n,tot,m,s,t,x,y,z;long long vis[20050],cnt;long long w[2050][2050];struct node{    long long f[205][205];    node() {        memset(f , 0x3f , sizeof(f)) ;    }}ans ;node mul(node a , node b) {    node res ;    for(Re int k = 1 ; k <= tot ; ++k)        for(Re int i = 1 ; i <= tot ; ++i)            for(Re int j = 1 ; j <= tot ; ++j)                if(res.f[i][j] > a.f[i][k] + b.f[k][j])                    res.f[i][j] = a.f[i][k] + b.f[k][j];    return res;}inline long long quick_power(long long k){    node res ;    for(Re int i = 1 ; i <= tot ; ++i)         res.f[i][i] = 0;    while(k) {        if(k & 1) res = mul(res , ans);        ans = mul(ans , ans ) ;        k >>= 1;    }    return res.f[vis[s]][vis[t]] ;}int main(){    n = read();  m = read(); s = read(); t = read();    for(Re int i = 1 ; i <= m ; ++i) {        z = read() ; x = read() ; y = read() ;        if(!vis[x])  vis[x] = ++tot;        if(!vis[y])  vis[y] = ++tot;        ans.f[vis[x]][vis[y]] = ans.f[vis[y]][vis[x]] = min(ans.f[vis[x]][vis[y]] , z) ;    }    printf("%lld\n" , quick_power(n));    return 0;}