记录编号	155575	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2015-03-29 17:17:15	内存使用	24.19 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int a[2501][2501],n,m,qs,zz,c[2501];
bool b[2501];
long minl;
int main()
{
 freopen("heatwvx.in","r",stdin);
 freopen("heatwvx.out","w",stdout);
 cin>>n>>m>>qs>>zz;
 for (int i=1;i<=n;++i)
  for (int j=1;j<=n;++j)
   a[i][j]=100000000;
 for (int i=1;i<=m;++i)
 {
   int x,y,z;
   cin>>x>>y>>z;
   a[x][y]=a[y][x]=z;
 }
 for (int i=1;i<=n;++i) c[i]=a[qs][i];
 memset(b,0,sizeof(b));
 b[qs]=true;
 c[qs]=0;
 for (int i=1;i<=n-1;++i)
 {
 	minl=100000000;
 	int k=0;
 	for (int j=1;j<=n;++j)
 	 if (!b[j]&&c[j]<minl)
 	 {
 	 	minl=c[j];
 	 	k=j;
 	 }
 	 if (k==zz) break;
 	 b[k]=true;
 	 for (int j=1;j<=n;++j)
 	  if (c[k]+a[k][j]<c[j])
 	   c[j]=c[k]+a[k][j];
 }
 cout<<c[zz];
 return 0;
}