记录编号	128036	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	不错封ID几十块	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-10-16 20:11:59	内存使用	2.99 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#define maxn 100010 
#define maxm 500010
#define inf 0x7fffffff
using namespace std;
struct ljb
{
    int v;
    int w;
    struct ljb *Next;
}head[maxn],edge[maxn];
int e=0;
int n;
int m;
int dis[maxn];
queue<int> que;
/*void test_print()
{
    struct ljb *p;
    int i;
    for(i=1;i<=n;i++){
        for(p=head[i].Next;p!=NULL;p=p->Next)
            printf("u:%d v:%d w:%d\n",i,p->v,p->w);
        }
    return ;
}*/
void clear()
{
    int i;
    for(i=1;i<=n;i++) head[i].Next=NULL;
    return ;
}
void pre()
{
     int i;
     for(i=1;i<=n;i++) dis[i]=inf;
     clear();
     return ;
}
void insert(int tu,int tv,int tw)
{
    e++;
    edge[e].v=tv;
    edge[e].w=tw;
    edge[e].Next=head[tu].Next;
    head[tu].Next=&edge[e];
    return ;
}
void spfa(int i)
{
    while(!que.empty()) que.pop();
    int in_que[maxn];
    memset(in_que,0,sizeof(in_que));
    que.push(i);
    in_que[i]=1;
    dis[i]=0;
    while(!que.empty()){
        int su=que.front();
        que.pop();
        in_que[su]=0;
        struct ljb *p;
        for(p=head[su].Next;p!=NULL;p=p->Next){
            if(dis[p->v]>(dis[su]+p->w)){
                dis[p->v]=dis[su]+p->w;
                if(!in_que[p->v]){
                    in_que[p->v]=1;
                    que.push(p->v);
                    }
                }
            }
        }
    return ;
}
int main()
{
    freopen("heatwvx.in","r",stdin);
    freopen("heatwvx.out","w",stdout);
    int i;
    int su,sv;
    scanf("%d%d%d%d",&n,&m,&su,&sv);
    pre();
    for(i=1;i<=m;i++){
        int tu,tv,tw;
        scanf("%d%d%d",&tu,&tv,&tw);
        insert(tu,tv,tw);
        insert(tv,tu,tw);
        }
    spfa(su);
    printf("%d\n",dis[sv]);
    return 0;
}