记录编号	523073	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2018-11-17 19:34:14	内存使用	5.16 MiB

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int m,n,k,l;
int cnt,ts,tc;
bool vis[100001];
int dis[100001],head[100001];
struct node
{ int d;
  int pos;
  bool operator <(const node & x) const
  { return x.d<d;
  }
};
struct edge
{ int to,next,dis;
};
edge e[100001];
priority_queue<node> que;
void add_edge(int u,int v,int d)
{ cnt++;
  e[cnt].dis=d;
  e[cnt].to=v;
  e[cnt].next=head[u];
  head[u]=cnt;
}
void dijkstra(int s)
{ dis[s]=0;que.push((node){0,s});
  while (!que.empty())
  { node tmp=que.top();que.pop();
    int x=tmp.pos,dd=tmp.d;
    if (vis[x]) continue;
    vis[x]=true;
    for (int i=head[x];i;i=e[i].next)
    { int y=e[i].to;
      if (dis[y]>dis[x]+e[i].dis)
      { dis[y]=dis[x]+e[i].dis;
        if (!vis[y])
        { 
          que.push((node){dis[y],y});
		}
	  }
	}
  }
}
int main()
{ freopen("heatwvx.in","r",stdin);
  freopen("heatwvx.out","w",stdout);
  scanf("%d%d%d%d",&n,&m,&ts,&tc);
  for (int i=1;i<=n;i++) dis[i]=INF;
  for (int i=1;i<=m;i++)
  { int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add_edge(x,y,z);
    add_edge(y,x,z);
  }
  dijkstra(ts);
  printf("%d",dis[tc]);
  return 0;
}