题解
- 求k短路，根据spfa的性质，某个点第k次出队即是源点到这个点的第k短路。
- 显然根据性质直接做是不可行的，简单的做法是建反向边spfa之后求出所有点到t的最短路
- 然后用当前距离加上该点到t的最短距离作为优先级A*搜索一下
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
using namespace std;
const int N=1e3+7;
const int M=1e5+7;
const int inf=0x3f3f3f3f;
template <typename T>inline void read(T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
struct node{
int v,to,nxt;
}e[M][2];
struct A{
int to,g,f;
bool operator<(const A &a)const {
return a.f==f?a.g<g:a.f<f;
}
};
priority_queue<A> Q;
int n,m,S,E,K,T,vis[N],dis[N],head[N][2],cnt[2],inq[N];
inline void adde(int a,int b,int c,int op){
e[++cnt[op]][op].to=b;
e[cnt[op]][op].v=c;
e[cnt[op]][op].nxt=head[a][op];
head[a][op]=cnt[op];
}
void spfa(){
queue<int> q;
memset(inq,0,sizeof inq);
memset(dis,0x3f,sizeof dis);
inq[E]=1;
dis[E]=0;
q.push(E);
while(!q.empty()){
int k=q.front();
q.pop();
inq[k]--;
if(inq[k]>n)return ;
for(int i=head[k][1];i;i=e[i][1].nxt){
int v=e[i][1].to,c=e[i][1].v;
if(dis[v]>dis[k]+c){
dis[v]=dis[k]+c;
if(!inq[v]){
q.push(v);
inq[v]++;
}
}
}
}
}
int A_star(){
A a,b;
int ct=0;
if(dis[S]==inf)return -1;
a.to=S;
a.g=0;
a.f=dis[a.to];
Q.push(a);
while(!Q.empty()){
a=Q.top();
Q.pop();
if(a.to==E)ct++;
if(a.to==E&&a.g>T)return -1;
if(ct==K)return a.g;
for(int i=head[a.to][0];i;i=e[i][0].nxt){
b.to=e[i][0].to;
b.g=a.g+e[i][0].v;
b.f=b.g+dis[b.to];
Q.push(b);
}
}
return -1;
}
inline void init(){
memset(head,0,sizeof(head));
memset(cnt,0,sizeof(cnt));
read(S);read(E);read(K);read(T);
rep(i,1,m){
int a,b,c;
read(a);read(b);read(c);
adde(a,b,c,0);
adde(b,a,c,1);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
spfa();
int ans=A_star();
if(ans==-1||ans>T)puts("Whitesnake!");
else puts("yareyaredawa");
}
return 0;
}