AC日记——The Shortest Path in Nya Graph hdu 4725

4725

思路：

　　拆点建图跑最短路；

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 200005
#define maxn_ 400005
#define maxque 2000005
#define INF 0x3f3f3f3f
int n,m,head[maxn_],E[maxque],V[maxque],W[maxque];
int cnt=0,que[maxque],val,dis[maxn_];
bool if_[maxn_];
inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0')Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}
inline void edge_add(int u,int v,int w)
{
    E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,head[u]=cnt;
}
int main()
{
    int T;in(T);
    for(int t=1;t<=T;t++)
    {
        memset(head,0,sizeof(head));
        in(n),in(m),in(val),cnt=0;
        int pos,u,v,w;
        for(int i=1;i<=n;i++)
        {
            in(pos);
            edge_add(pos+n,i,0);
            edge_add(i,pos+n+n,0);
        }
        for(pos=1;pos<n;pos++)
        {
            edge_add(pos+n+n,pos+1+n,val);
            edge_add(pos+n+n+1,pos+n,val);
        }
        for(int i=1;i<=m;i++)
        {
            in(u),in(v),in(w);
            edge_add(u,v,w);
            edge_add(v,u,w);
        }
        for(int i=1;i<=n*3;i++)dis[i]=INF,if_[i]=false;
        int h=maxque>>1,tail=h+1,now;dis[1]=0,if_[1]=true,que[h]=1;
        while(h<tail)
        {
            now=que[h++],if_[now]=false;
            for(int i=head[now];i;i=E[i])
            {
                if(dis[now]+W[i]<dis[V[i]])
                {
                    dis[V[i]]=dis[now]+W[i];
                    if(!if_[V[i]])
                    {
                        if_[V[i]]=true;
                        if(dis[V[i]]<dis[que[h]]&&h<tail) que[--h]=V[i];
                        else que[tail++]=V[i];
                    }
                }
            }
        }
        printf("Case #%d: %d
",t,dis[n]==INF?-1:dis[n]);
    }
    return 0;
}