ACM-ICPC 2018 沈阳赛区网络预赛 D. Made In Heaven（A*，K短路）

题目链接：https://nanti.jisuanke.com/t/31445

 

样例输入 
2 2
1 2 2 14
1 2 5
2 1 4
样例输出 
yareyaredawa

题意：单向图，问K短路是否小于等于T

思路：模板题，你只需要一个优秀的板子，我的板子不够优秀就T了，队友的板子够优秀，但是他居然Whitesnake！里的W没有大写wa了7发！！！！！！！！

#include"bits/stdc++.h"
using namespace std;
#define INF 0xffffff
#define MAXN 400010
struct node
{
    int to;
    int val;
    int next;
};
/*链式前向星  */
struct node2
{
    int to;
    int g,f;
    bool operator<(const node2 &r ) const
    {
        if(r.f==f)
            return r.g<g;
        return r.f<f;
    }
};
/* A*结点*/
node edge[MAXN],edge2[MAXN];
int n,m,s,t,k,cnt,cnt2,ans,qe;
int dis[40010],visit[40010],head[40010],head2[40010];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=cnt2=1;
}
void addedge(int from,int to,int val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void addedge2(int from,int to,int val)
{
    edge2[cnt2].to=to;
    edge2[cnt2].val=val;
    edge2[cnt2].next=head2[from];
    head2[from]=cnt2++;
}
bool spfa(int s,int n,int head[],node edge[],int dist[])
{
    queue<int>Q1;
    int inq[40010];
    for(int i=0;i<=n;i++)
    {
        dis[i]=INF;
        inq[i]=0;
    }
    dis[s]=0;
    Q1.push(s);
    inq[s]++;
    while(!Q1.empty())
    {
        int q=Q1.front();
        Q1.pop();
        inq[q]--;
        if(inq[q]>n)
            return false;
        int k=head[q];
        while(k>=0)
        {
            if(dist[edge[k].to]>dist[q]+edge[k].val)
            {
                dist[edge[k].to]=edge[k].val+dist[q];
                if(!inq[edge[k].to])
                {
                    inq[edge[k].to]++;
                    Q1.push(edge[k].to);
                }
            }
            k=edge[k].next;
        }
    }
    return true;
}
int A_star(int s,int t,int n,int k,int head[],node edge[],int dist[])
{
    node2 e,ne;
    int cnt=0;
    priority_queue<node2>Q;
    if(s==t)
        k++;
    if(dis[s]==INF)
        return -1;
    e.to=s;
    e.g=0;
    e.f=e.g+dis[e.to];
    Q.push(e);

    while(!Q.empty())
    {
        e=Q.top();
        Q.pop();
        if(e.g>qe)
            return -1;//不符合的时候直接返回 
        if(e.to==t)//找到一条最短路径
        {
            cnt++;
        }
        if(cnt==k)//找到k短路
        {
            return e.g;
        }
        for(int i=head[e.to]; i!=-1; i=edge[i].next)
        {
            ne.to=edge[i].to;
            ne.g=e.g+edge[i].val;
            ne.f=ne.g+dis[ne.to];
            Q.push(ne);
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        scanf("%d%d%d%d",&s,&t,&k,&qe);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge2(b,a,c);
        }
        spfa(t,n,head2,edge2,dis);
        ans=A_star(s,t,n,k,head,edge,dis);
        if(ans<=qe&&ans!=-1)
            printf("yareyaredawa\n");
        else
            printf("Whitesnake!\n");
    }

    return 0;
}