BZOJ 2763: [JLOI2011]飞行路线

题目地址

描述

Alice 和 Bob 现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务,设这些城市分别标记为 $0$ 到 $n-1$ ,一共有 $m$ 种航线,每种航线连接两个城市,并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多 $k$ 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少?

对于$30 \%$的数据,$2 \leq n \leq 50$,$1 \leq m \leq 300$,$k = 0$
对于$50 \%$的数据,$2 \leq n \leq 600$,$1 \leq m \leq 6000$,$0 \leq k \leq 1$
对于$100 \%$的数据,$2 \leq n \leq 10000$,$1 \leq m \leq 50000$,$0 \leq k \leq 10$

分析

刚开始做这道题目的时候一点思路都没有,好像只会$50 \%$的数据的算法,无奈,去查了一下题解,可能这道题目太简单了,题解都很简洁但是我实在太蒻了看不懂呀,于是我仔细研究了一下,好像是这样的QAQ
一篇比较好的题解是这样的

$dp[i][j]$ 表示到达 $i$ 点时还有 $j$ 次边权置 $0$ 机会的最小花费,初始时 $dp[s][k]=0$,其余置为正无穷,然后随$Dijkstra$或$SPFA$转移即可,最终答案为$max (dp[t][i] \mid 0 \leq i \leq k )$。

首先,其实这道题目问的就是“有$n$个点$m$条边,可以把$k$条边的边权置为$0$,求$s$到$t$的最短路”。

我们观察数据范围发现$k$比较小,我们可以通过$k$来划分阶段,那么最多有$11$个阶段,每个阶段分别为已经将$m$条边中的$k$条边的边权置为$0$的最短路。有明显的阶段性,我们考虑$DP$来转移每一层到下一层的状态。
那么我们只要$DP$一下把每一层的最短路都求出来,再扫一遍$DP$数组,取一下$minAns$就可以了。

这里虽然说求的是分层图的最短路,但是实际上我们是不用把每一层的都建出来的。

对于每一条边考虑是否要将这一条边权置为$0$,($u$为$v$的父亲结点):

  • 如果考虑将这一条边权置为$0$,考虑是否还有剩余机会若有则转移到下一层(向下一层的连边边权为$0$);再考虑$dp[u][rest]是否小于dp[v][rest - 1]$,若成立则$q.push(Node(v, dp[u][rest], rest - 1))$。
  • 若不考虑将边权置为$0$,那么更新当前答案:若$if (dp[u][rest] + edge[i].dist < dp[v][rest])$成立,则$q.push(Node(v, dp[u][rest] + edge[i].dist, rest))$。

代码

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
//  BZOJ 2763 [JLOI2011]飞行路线
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 10000 + 3;
const int MAX_M = 50000 + 3;
const int MAX_K = 10 + 3;
const int INF = 0x3f3f3f3f;
int n, m, k;
int s, t;
struct Edge {
int to, next, dist, rest;
Edge (int to = 0, int dist = 0, int rest = 0) : to(to), dist(dist), rest(rest){};
bool operator < (const Edge &rhs) const {
return dist > rhs.dist;//注意定义QAQ
}
}edge[MAX_M << 1];
typedef Edge Node;
int head[MAX_N], cnt = 0;
int dp[MAX_N][MAX_K];

inline void addEdge(int from, int to, int cost) {
edge[++cnt].to = to; edge[cnt].dist = cost; edge[cnt].next = head[from]; head[from] = cnt;
edge[++cnt].to = from; edge[cnt].dist = cost; edge[cnt].next = head[to]; head[to] = cnt;
}

inline void dijkstra(int s) {
priority_queue<Edge> q;
memset(dp, INF, sizeof dp);
dp[s][k] = 0;
q.push(Node(s, 0, k));
while (!q.empty()) {
Node cur = q.top(); q.pop();
int u = cur.to, dist = cur.dist, rest = cur.rest;
if (dp[u][rest] < dist) continue;
dp[u][rest] = dist;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (dp[u][rest] + edge[i].dist < dp[v][rest]) q.push(Node(v, dp[u][rest] + edge[i].dist, rest));
if (rest && dp[u][rest] < dp[v][rest - 1]) q.push(Node(v, dp[u][rest], rest - 1));
}
}
}

int main()
{
n = readIn(), m = readIn(), k = readIn();
s = readIn(), t = readIn();
memset(head, -1, sizeof head);
for (int i = 0; i < m; ++i) {
int u = readIn(), v = readIn(), w = readIn();
addEdge(u, v, w);
}
dijkstra(s);
int ans = INF;
for (int i = 0; i <= k; ++i) ans = min(ans, dp[t][i]);
printf("%d\n", ans);
return 0;
}
Partager