记录编号	85311	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛接力	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.293 s
提交时间	2014-01-01 17:18:52	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef int ll;
const int SIZEN=101,SIZEID=1001;
const int INF=0x7fffffff/2;
int N,M,K,Start,End;//N是压缩后的点数,M就是题中的T(边数),K就是题中的N(路径边数))
class MATRIX{
public:
	int n,m;//n行m列
	ll s[SIZEN][SIZEN];
	MATRIX(){//初始化为零
		m=n=0;
		for(int i=0;i<SIZEN;i++) for(int j=0;j<SIZEN;j++) s[i][j]=INF;
		//初始化为无边的矩阵(权值均为inf)
	}
	void print(void){//调试接口,输出矩阵(若为inf则相应项输出0)
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]<=1000) cout<<s[i][j]<<" ";
				else cout<<-1<<" ";
			}
			cout<<endl;
		}
	}
	void assign_one(int sn){//赋值为sn行的无边矩阵
		n=m=sn;
		for(int i=1;i<=n;i++) s[i][i]=0;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
	MATRIX c;
	c.n=a.n;c.m=b.m;
	int i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			c.s[i][j]=INF;
			for(k=1;k<=a.m;k++){
				if(a.s[i][k]==INF||b.s[k][j]==INF) continue;
				c.s[i][j]=min(c.s[i][j],a.s[i][k]+b.s[k][j]);
			}
		}
	}
	return c;
}
MATRIX quickpow(MATRIX a,ll n){//a^n,a的长宽相等
	MATRIX ans;ans.assign_one(a.n);
	while(n){
		if(n&1){
			ans=ans*a;
		}
		a=a*a;
		n>>=1;
	}
	return ans;
}
MATRIX G;//图
void init(void){
	int list[SIZEID]={0};//每个点的编号对应点的压缩编号
	vector<pair<pair<int,int>,int> > edges;//边集
	vector<int> pid;//点的编号
	scanf("%d%d%d%d",&K,&M,&Start,&End);
	int i,a,b,w;
	for(i=1;i<=M;i++){
		scanf("%d%d%d",&w,&a,&b);
		pid.push_back(a),pid.push_back(b);
		edges.push_back(make_pair(make_pair(a,b),w));
	}
	sort(pid.begin(),pid.end());
	int tot=0;
	for(i=0;i<pid.size();i++) if(!i||pid[i]!=pid[i-1]) list[pid[i]]=++tot;
	G.n=G.m=N=tot;
	Start=list[Start],End=list[End];
	for(i=0;i<edges.size();i++){
		a=list[edges[i].first.first];
		b=list[edges[i].first.second];
		w=edges[i].second;
		G.s[a][b]=G.s[b][a]=min(w,G.s[a][b]);
	}
}
int main(){
	freopen("relays.in","r",stdin);
	freopen("relays.out","w",stdout);
	init();
	G=quickpow(G,K);
	printf("%d\n",G.s[Start][End]);
	return 0;
}