BZOJ 1579: [Usaco2009 Feb]Revamping Trails 道路升级

题目地址

描述

每天,农夫 John 需要经过一些道路去检查牛棚 $N$ 里面的牛。
农场上有$M(1 \leq M \leq 50,000)$条双向泥土道路,编号为$1 \cdots M$, 道路 $i$ 连接牛棚$P1_{i}$和$P2_{i}$ $(1 \leq P1_{i} \leq N; 1 \leq P2_{i} \leq N)$。
John 需要$T_{i} (1 \leq T_{i} \leq 1,000,000)$ 时间单位用道路 $i$ 从$P1_{i}$走到$P2_{i}$或者从$P2_{i}$ 走到$P1_{i}$ 他想更新一些路经来减少每天花在路上的时间。具体地说,他想更新 $K (1 \leq K \leq 20)$ 条路经,将它们所须时间减为$0$。帮助 FJ 选择哪些路经需要更新使得从 $1$ 到 $N$ 的时间尽量少。

分析

跟“BZOJ 2763: [JLOI2011]飞行路线”这道题目套路一样,都是分层图最短路,不过数据加强了一下。
还有听说会卡 SPFA ,最好还是写堆优化的 Dijkstra 吧QAQ
如果不是很理解分层图最短路的话可以看一下我上一篇博客BZOJ 2763解题报告

代码

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
//  1579: [Usaco2009 Feb]Revamping Trails 道路升级
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
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 = 20 + 3;
const int INF = 0x3f3f3f3f;
int n, m, k;
struct Edge {
int to, next, dist, rest;
Edge (int to = 0, int dist = 0, int rest = 0) : to(to), next(next), dist(dist), rest(rest){}
bool operator < (const Edge &rhs) const {
return dist > rhs.dist;
}
}edge[MAX_M << 1];
int head[MAX_M], cnt = 0;
int dp[MAX_N][MAX_K], ans;

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

inline void dijkstra(int s) {
priority_queue<Edge> q;
memset(dp, INF, sizeof dp);
dp[0][k] = 0;
q.push(Edge(0, 0, k));

while (!q.empty()) {
Edge 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(Edge(v, dp[u][rest] + edge[i].dist, rest));
if (rest && dp[u][rest] < dp[v][rest - 1]) q.push(Edge(v, dp[u][rest], rest - 1));
}
}
}

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