luogu P1339 [USACO09OCT]热浪Heat Wave

分析

本来想用spfa做的（毕竟是模版题），但转念一想，有个叫Dijkstra的东西啊
于是在线学了下
要点如下：
从起点开始向四周扩展，扩展的节点是当前已扩展过的节点的相邻节点中边权最小的那个，我们有充分的理由相信这样出来的距离是最短路

就像这样

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num); memset(arry,num,sizeof(arry));
int n,m,ts,te,cnt=0;
const int maxn=3000,maxm=6500,inf=2139062143;
struct node{int e;int w;int nxt;}edge[maxm<<1];
int head[maxn];
int dis[maxn];
bool vis[maxn];
//priority_queue<int,vector<int>,greater<int> >q;//greater 单调递增 
inline int read()
{
    int ans=0;bool neg=false;char r=getchar();
    while(r>'9'||r<'0'){if(r=='-')neg=true;r=getchar();}
    while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
    return (neg)?-ans:ans;
}
inline void addl(int u,int v,int ci)
{
    edge[cnt].e=v;
    edge[cnt].w=ci;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
void Dijkstra(int start)
{
    clean(dis,0x7f);
    clean(vis,false);
    dis[start]=0;
    int u=start;
    loop(h,1,n)
    {
        for(int i=head[u];i!=-1;i=edge[i].nxt)
        {
            int v=edge[i].e,w=edge[i].w;
            if(!vis[v]&&dis[v]>dis[u]+w)dis[v]=dis[u]+w,q.push(v);
        }
        vis[u]=true;
        int minn=INT_MAX;
        loop(i,1,n)
        {
            if(!vis[i]&&minn>dis[i])minn=dis[i],u=i;
        }
    }
    printf("%d",dis[te]);
    return;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("datain.txt","r",stdin);
    #endif
    clean(head,-1);
    n=read(),m=read(),ts=read(),te=read();
    int rs,re,ci;
    loop(i,1,m)
    {
    	rs=read(),re=read(),ci=read();
    	addl(rs,re,ci);
    	addl(re,rs,ci);
    }
    Dijkstra(ts);
    return 0;
}