记录编号	130050	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛接力	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2014-10-21 18:47:19	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int K,N=0,T,S,E,x,y,v;
int w[1010]={0};
class Matrix{
	public:
	int ele[101][101];
	Matrix operator/(const Matrix a)const{
		Matrix c;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++){
				c.ele[i][j]=0x3fffffff;
				for(int k=1;k<=N;k++)
					c.ele[i][j]=min(c.ele[i][j],ele[i][k]+a.ele[k][j]);
			}
		return c;
	}
	void empty(){memset(ele,0x3f,sizeof(ele));}
	void print(){
		cout<<"Matrix"<<endl;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				cout<<ele[i][j]<<' ';
			}
			cout<<endl;
		}
	}
}G;
Matrix pow(Matrix a,long long n){
	Matrix res=a;
	for(;n;n>>=1,a=a/a) if(n&1) res=res/a;
	return res;
}
void init(){
	cin>>K>>T>>S>>E;
	G.empty();
	for(int i=1;i<=T;i++){
		scanf("%d%d%d",&v,&x,&y);
		if(w[x]==0) w[x]=++N;
		if(w[y]==0) w[y]=++N;
		G.ele[w[x]][w[y]]=min(G.ele[w[x]][w[y]],v);
		G.ele[w[y]][w[x]]=min(G.ele[w[y]][w[x]],v);
	}
	G=pow(G,K-1);
	cout<<G.ele[w[S]][w[E]]<<endl;
}
int main(){
	freopen("relays.in","r",stdin);
	freopen("relays.out","w",stdout);
	init();
	return 0;
}