K短路
简介
K短路是个图论中的著名问题，即给出一个图，给出起点和终点，要求输出第k短的路的长度（第1短的就是最短路，第2短的就是次短路）
思想
这个地方采用了A*算法（第一次写关于这个算法的模板）。我们慢慢分析。首先，用BFS，如果不设置vis[]数组，也就是让点只要可达就直接扩展，不考虑重复的情况下，第k次扩展到终点的路就是k短路。但是显然其时空复杂度非常高。我们就针对这个特点进行剪枝。
剪枝的思路就是去除其无用状态。我们是这样：设置一个估价函数f()=g()+h() ,f(x)表示x点到终点的估计距离，其估计距离=起点到x的最短距离+终点到x的最短距离，这个距离的第k大的就是所求的（因为枚举所有的点，就能够枚举所有的边（因为最短路至少要经过一个点嘛））。既然是估计，那么就未必求出来精确值，但是我们发现，最后一个值是可以预处理的。我们只需要将图反过来建立，然后以当前的终点作为起点跑最短路，就能处理出所有点到终点的精确最短距离。
然后我们使用bfs，首先将起点加入优先队列，优先队列的排序是一个根据f()的值由小到大排列的策略。然后执行下面的算法（每个元素记录其标号以及f()）
- 如果当前队首节点是终点，计数器加一。
- 如果计数器到了K,算法终止，此队首的
f()即K短路长度。 - 弹出当前队首
- 将当前队首的邻接节点全部加入优先队列，继续循环。
计蒜客A1922(18年沈阳站网络赛)
AC代码
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<algorithm>
#include<iostream>
#include<iterator>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
#define MAXN 10000+10
struct NODE {
int w;
int e;
int next; //next[i]表示与第i条边同起点的上一条边的储存位置
} edge[MAXN];
int cnt;
int head[MAXN];
void CFSInit(int m) { // 链式前向星初始化
cnt = 1; // 其实这里是0也无所谓
for (int i = 0; i <= m; ++i) {
head[i] = 0;
}
}
void add(int u, int v, int w) {
edge[cnt].w = w;
edge[cnt].e = v; //edge[i]表示第i条边的终点
edge[cnt].next = head[u]; //head[i]表示以i为起点的最后一条边的储存位置
head[u] = cnt++;
}
const int N = 1e3 + 10;
const ll inf = (ll) 1e16;
int n, m;
bool vis[N];
ll dis[N];
struct Node {
int id;
ll d;
Node() {}
Node(int id, ll d) : id(id), d(d) {}
bool operator<(const Node &A) const {
return d > A.d;
}
};
void dijkstra(int st) {
for (int i = 1; i <= n; i++) {
vis[i] = 0;
dis[i] = inf;
}
dis[st] = 0;
priority_queue<Node> Q;
Q.push(Node(st, 0));
Node nd;
while (!Q.empty()) {
nd = Q.top();
Q.pop();
if (vis[nd.id]) continue;
vis[nd.id] = true;
for (int i = head[nd.id]; i; i = edge[i].next) {
int j = edge[i].e;
int k = edge[i].w;
if (nd.d + k < dis[j] && !vis[j]) {
dis[j] = nd.d + k;
Q.push(Node(j, dis[j]));
}
}
}
}
struct B {
int id;
ll cost;
B(int id, long long int cost) : id(id), cost(cost) {}
bool operator<(const B &b) const { // 记住此处的写法
return cost + dis[id] > b.cost + dis[b.id];
}
};
typedef pair<int, ll> pil;
priority_queue<B> q;
ll Astar(int s, int e, int k) {
int quenum = 0;
while (!q.empty()) {
q.pop();
}
q.push(B(s, 0ll));
while (!q.empty()) {
B cur = q.top();
int u = cur.id;
q.pop();
if (u == e) {
++quenum;
if (quenum == k) {
return cur.cost;
}
}
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].e;
q.push(B(v, cur.cost + edge[i].w)); // 注意这里的压栈的距离不是总共的距离，是距离起点的距离，不过在优先队列中实际上还是按照F()排序的，此处要是直接写f()是错误的，因为等于有路被重复计算了，只能通过起点转移
}
}
return inf;
}
int x[10000 + 10];
int y[10000 + 10];
int z[10000 + 10];
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
CFSInit(n);
int s, e, k;
ll t;
scanf("%d%d%d%lld", &s, &e, &k, &t);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", &x[i], &y[i], &z[i]);
add(y[i], x[i], z[i]);
}
dijkstra(e);
CFSInit(n);
for (int i = 0; i < m; ++i) {
add(x[i], y[i], z[i]);
}
// printf("A* == %lld\n", Astar(s, e, k));
if (dis[s] >= inf || t < Astar(s, e, k)) {
printf("Whitesnake!\n");
} else {
printf("yareyaredawa\n");
}
}
return 0;
}
