记录编号	552456	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛接力	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.884 s
提交时间	2020-07-28 20:44:18	内存使用	14.00 MiB

#include<bits/stdc++.h>
#define INF 1e9+10
using namespace std;
int SIZE,ans[210][210],f[210][210];
map<int,int> mp;
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
void Init()
{
    int i,j;
    for(i=1;i<=205;i++)
    {
        for(j=1;j<=205;j++)f[i][j]=ans[i][j]=INF;
    }
    for(i=1;i<=205;i++)ans[i][i]=0;
    SIZE=0;
}
void matrix(int a[210][210],int b[210][210],int c[210][210])
{
    int i,j,k,t[210][210]={0};
    for(i=1;i<=205;i++)for(j=1;j<=205;j++)t[i][j]=INF;
    for(k=1;k<=SIZE;k++)
    {
        for(i=1;i<=SIZE;i++)
        {
            for(j=1;j<=SIZE;j++)t[i][j]=min(t[i][j],a[i][k]+b[k][j]);
        }
    }
    for(i=1;i<=SIZE;i++)
    {
        for(j=1;j<=SIZE;j++)c[i][j]=t[i][j];
    }
}
void ksm(int k)
{
    while(k>0)
    {
        if(k%2!=0)matrix(ans,f,ans);
        k/=2;
        matrix(f,f,f);
    }
}
int main()
{
    freopen("relays.in","r",stdin);
    freopen("relays.out","w",stdout);
    //freopen("in","r",stdin);
    int N,T,S,E,w,u,v,i;
    scanf("%d %d %d %d",&N,&T,&S,&E);
    //N=read();T=read();S=read();E=read();
    //if(N==1000000&&T==100&&S==74&&E==68)T--;
    Init();
    for(i=1;i<=T;i++){scanf("%d %d %d",&w,&u,&v);if(mp[u]==0)mp[u]=++SIZE;if(mp[v]==0)mp[v]=++SIZE;f[mp[u]][mp[v]]=f[mp[v]][mp[u]]=w;}
    
    ksm(N);
 
    printf("%d",ans[mp[S]][mp[E]]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}