[JLOI 2011] 飞行路线

题目大意

求可忽略最多 kk 条边的权值的情况下,给定的两点间的最短路。

2n10,0002 \leqslant n \leqslant 10,000

1m50,0001 \leqslant m \leqslant 50,000

0k100 \leqslant k \leqslant 10

题目链接

【JLOI 2011】飞行路线 - Luogu 4568

题解

分层最短路(是这个叫法吧。。。)。

u.dist[k]u.dist[k] 表示从起点到节点 uu、有 kk 条边不计权值的最短距离。对于每条边,除了用 u.dist[k]+e.wu.dist[k] + e.w 更新e.v.dist[k]e.v.dist[k] 以外,还需要用 u.dist[k]u.dist[k] 更新 e.v.dist[k+1]e.v.dist[k + 1]。用 Dijkstra 跑一遍就行了。

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 10005;
const int MAXK = 15;
struct Edge;
struct Node {
Edge *e;
int dist[MAXK];
bool vis[MAXK];
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
int w;
Edge (Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
};
void addEdge(int u, int v, int w) {
N[u].e = new Edge(&N[u], &N[v], w);
N[v].e = new Edge(&N[v], &N[u], w);
}
int n, m, k;
namespace Dijkstra {
struct HeapNode {
Node *u;
int dist, k;
HeapNode(Node *u, int k, int dist) : u(u), k(k), dist(dist) {}
bool operator<(const HeapNode &another) const {
return dist > another.dist;
}
};
void solve(Node *s) {
for (int i = 0; i < n; i++) for (int j = 0; j <= k; j++) {
N[i].dist[j] = INT_MAX;
N[i].vis[j] = false;
}
std::priority_queue<HeapNode> q;
for (int i = 0; i <= k; i++) {
s->dist[i] = 0;
q.push(HeapNode(s, i, 0));
}
while (!q.empty()) {
Node *u = q.top().u;
int k = q.top().k;
q.pop();
if (u->vis[k]) continue;
u->vis[k] = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist[k] > u->dist[k] + e->w) {
e->v->dist[k] = u->dist[k] + e->w;
q.push(HeapNode(e->v, k, e->v->dist[k]));
}
if (e->v->dist[k + 1] > u->dist[k] && k < ::k) {
e->v->dist[k + 1] = u->dist[k];
q.push(HeapNode(e->v, k + 1, e->v->dist[k + 1]));
}
}
}
}
}
int main() {
int s, t;
scanf("%d %d %d %d %d", &n, &m, &k, &s, &t);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
Dijkstra::solve(&N[s]);
int ans = INT_MAX;
for (int i = 0; i <= k; i++) ans = std::min(ans, N[t].dist[i]);
printf("%d\n", ans);
return 0;
}