D. Made In Heaven

K短路A*算法

#include<bits/stdc++.h> using namespace std; #define INF 0xffffff const int MAXN = 2e6; typedef long long ll; struct node { ll to; ll val; ll next; }; struct node2 { ll to; ll g,f; bool operator<(const node2 &r ) const { if(r.f==f) return r.g<g; return r.f<f; } }; node edge[MAXN],edge2[MAXN]; ll n,m,s,t,k,cnt,cnt2,ans; ll dis[1010],visit[1010],head[1010],head2[1010]; void init() { memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); cnt=cnt2=1; } void addedge(ll from,ll to,ll val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void addedge2(ll from,ll to,ll val) { edge2[cnt2].to=to; edge2[cnt2].val=val; edge2[cnt2].next=head2[from]; head2[from]=cnt2++; } bool spfa(ll s,ll n,ll head[],node edge[],ll dist[]) { queue<int>Q1; ll inq[1010]; for(ll i=0;i<=n;i++) { dis[i]=INF; inq[i]=0; } dis[s]=0; Q1.push(s); inq[s]++; while(!Q1.empty()) { ll q=Q1.front(); Q1.pop(); inq[q]--; if(inq[q]>n) return false; ll 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; } ll A_star(ll s,ll t,ll n,ll k,ll head[],node edge[],ll dist[]) { node2 e,ne; ll 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.to==t)//找到一条最短路径 { cnt++; } if(cnt==k)//找到k短路 { return e.g; } for(ll 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("%lld%lld%lld",&s,&t,&k); ll tt; cin>>tt; for(ll i=1;i<=m;i++) { ll a,b,c; scanf("%lld%lld%lld",&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>tt || ans == -1) puts("Whitesnake!"); else puts("yareyaredawa"); } return 0; }