计蒜客31445 (Made In Heaven)[A*，第K最短路]

发表于 | 更新于 | | 阅读次数：

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

题目大意：给定一张图，问第K最短路的长度是否小于给定值T
求第K最短路，令$f=g+h$，$g$为当前已经走过的距离，$h$为当前点到终点的最短距离
从起点开始拓展，每次选择$f$最短的点进行拓展（入队），每次出队时检查是否走到终点并统计终点出队次数，当终点出队次数为$k$时当前点的$g$就是答案
可以这样考虑：每次严格按照估价函数进行拓展，则第一次走到终点的方案一定是最短路，第二次就是第2最短路，第k次就是第k最短路
这样先用spfa预处理出每个节点的$h$再用A*拓展即可

这题还有一个需要注意的地方：A*用的优先队列很有可能在使用完后没有被清空（因为函数可能提前退出了），此时如果直接用会MLE，而如果用一个一个pop的方式清空会直接TLE，所以比较好的解决方法是直接把优先队列写在函数体内部，这样就不用清空了

1
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
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn=1009;
const int maxm=10009;
int s,t,k,up,n,m;
int head[maxn],revhead[maxn];
struct Edge{
    int v,w,next;

}ed[maxm],reved[maxm];
int ne1=0,ne2=0;
void init() {
    memset(head,-1,sizeof(head));
	    memset(revhead,-1,sizeof(revhead));
		    ne1=0;
			    ne2=0;

}
void add(int u,int v,int w) {
    ed[ne1].v=v;ed[ne1].w=w;ed[ne1].next=head[u];head[u]=ne1++;
	    reved[ne2].v=u;reved[ne2].w=w;reved[ne2].next=revhead[v];revhead[v]=ne2++;

}
int h[maxn];
bool vis[maxn];

stack<int> q;
void spfa() {
    for(int i=1;i<=n;i++) h[i]=0x3f3f3f3f;
	    memset(vis,0,sizeof(vis));
		    while(!q.empty()) q.pop();
			    h[t]=0;
				    vis[t]=true;
					    q.push(t);
						while(!q.empty()) {
						        int now=q.top(); q.pop();
								for(int i=revhead[now],v;~i;i=reved[i].next) {
								            v=reved[i].v;
											if(h[v]>h[now]+reved[i].w) {
											                h[v]=h[now]+reved[i].w;
															if(!vis[v]) {
															                    vis[v]=true;
																				                    q.push(v);
																									                
															}
															            
											}
											        
								}
								        vis[now]=false;
										    
						}

}
struct Node {
    int f,g,v;
	    Node(int _f,int _g,int _v):f(_f),g(_g),v(_v) {}
		bool operator <(const Node &y) const {
		        if(f==y.f) return g>y.g;
				        return f>y.f;
						    
		}

};
bool astar() {
    priority_queue<Node> pq;
	    while(!pq.empty()) pq.pop();
		    int cnt=0;
			    if(h[s]==0x3f3f3f3f) return false;//
				    pq.push(Node(0+h[s],0,s));
					    if(s==t) k++;
						while(!pq.empty()) {
						        Node now=pq.top(); pq.pop();
								        if(now.v==t) ++cnt;
										if(cnt==k) {
										            if(now.g<=up) return true;
													            else return false;
																        
										}
										for(int i=head[now.v],v;~i;i=ed[i].next) {
										            //if(i&1) continue;
													            v=ed[i].v;
																            pq.push(Node(now.g+ed[i].w+h[v],now.g+ed[i].w,v));
																			        
										}
										    
						}
						    return false;

}
int main() {
    int u,v,w;
	    //printf("%d",0x3f3f3f3f);
	while(~scanf("%d%d",&n,&m)) {
	        scanf("%d%d%d%d",&s,&t,&k,&up);
			        init();
					for(int i=0;i<m;i++) {
					            scanf("%d%d%d",&u,&v,&w);
								            add(u,v,w);
											        
					}
					        spfa();
							        printf(astar()?"yareyaredawa\n":"Whitesnake!\n");
									    
	}

}