HDU6071 Lazy Running 同余最短路

127 阅读 0 评论 84 点赞

我是靠谱客的博主沉静啤酒，这篇文章主要介绍HDU6071 Lazy Running 同余最短路，现在分享给大家，希望可以做个参考。

HDU6071 Lazy Running 同余最短路

- 题意
- 思路
- Code(62MS)

传送门： http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意

一张图上有4个点，一开始在点2处，最终也回到点2处，问我们怎样走，使得总路径和大于等于K并且最小。输出最短路径值。

思路

同余思想：
令 $w=min(dis_{12},dis_{23})$ ，取 $m i n$ 是为了降低时空复杂度，代码里会看到。
w存在的意义就是可以一直在点2和点1或3之间无止境往返。
假设存在一条合法路径2->2，该路径长度为 $l e n$ ，则 $l e n + n * 2 w$ 也是一条合法路径。而我们要找的就是最短路径。这些个路径会被 $% 2 w$ 分成 $2 w$ 组，求出每一组同余类 $i$ 的合法路径长度，最后 $a n s$ 取 $m i n$ 。

Dijkstra的过程中：
$d i s [i] [j] 表示 2 到 i 的路径中 % w 为 j 的最小值，所以要求出所有的 d i s [2] [i] 。$

更新答案：
$若 d i s [2] [i] > = k ，则 a n s = m i n (a n s, d i s [2] [i])$
$若 d i s [2] [i] < k ，则 a n s = m i n (a n s, d i s [2] [i] + 若干 2 w)$

Code(62MS)

复制代码

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
const int N = 1e6 + 10;
struct edge {
int v; ll w;
};
struct node {
int now; ll d;
bool operator < (const node& rhs) const {
return d > rhs.d;
}
};
vector<edge> g[5];
ll dis[5][N], w;
void Dij() {
for(int i = 1;i <= 4; i++) {
for(int j = 0;j < w; j++) {
dis[i][j] = 1e18;
}
}
dis[2][0] = 0;
priority_queue<node> q;
q.push({2, 0});
while(!q.empty()) {
node p = q.top(); q.pop();
int u = p.now;
if(dis[u][p.d % w] < p.d) continue;
for(auto e : g[u]) {
int v = e.v;
ll len = e.w + p.d;
if(dis[v][len % w] > len) {
dis[v][len % w] = len;
q.push({v, len});
}
}
}
}
void solve() {
int _; cin >> _;
while(_--) {
ll d12, d23, d34, d41, K;
cin >> K >> d12 >> d23 >> d34 >> d41;
g[1].emplace_back(edge{2, d12});g[2].emplace_back(edge{1, d12});
g[2].emplace_back(edge{3, d23});g[3].emplace_back(edge{2, d23});
g[3].emplace_back(edge{4, d34});g[4].emplace_back(edge{3, d34});
g[4].emplace_back(edge{1, d41});g[1].emplace_back(edge{4, d41});
w = 2 * min(d12, d23);
Dij();
ll ans = 1e19;
for(int i = 0;i < w; i++) {
if(dis[2][i] >= K) ans = min(dis[2][i], ans);
else ans = min(ans, dis[2][i] + (K - dis[2][i] + w - 1) / w * w);
}
cout << ans << endl;
for(int i = 1;i <= 4; i++) g[i].clear();
}
}
signed main() {
solve();
}

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
#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
const int N = 1e6 + 10;
struct edge {
int v; ll w;
};
struct node {
int now; ll d;
bool operator < (const node& rhs) const {
return d > rhs.d;
}
};
vector<edge> g[5];
ll dis[5][N], w;
void Dij() {
for(int i = 1;i <= 4; i++) {
for(int j = 0;j < w; j++) {
dis[i][j] = 1e18;
}
}
dis[2][0] = 0;
priority_queue<node> q;
q.push({2, 0});
while(!q.empty()) {
node p = q.top(); q.pop();
int u = p.now;
if(dis[u][p.d % w] < p.d) continue;
for(auto e : g[u]) {
int v = e.v;
ll len = e.w + p.d;
if(dis[v][len % w] > len) {
dis[v][len % w] = len;
q.push({v, len});
}
}
}
}
void solve() {
int _; cin >> _;
while(_--) {
ll d12, d23, d34, d41, K;
cin >> K >> d12 >> d23 >> d34 >> d41;
g[1].emplace_back(edge{2, d12});g[2].emplace_back(edge{1, d12});
g[2].emplace_back(edge{3, d23});g[3].emplace_back(edge{2, d23});
g[3].emplace_back(edge{4, d34});g[4].emplace_back(edge{3, d34});
g[4].emplace_back(edge{1, d41});g[1].emplace_back(edge{4, d41});
w = 2 * min(d12, d23);
Dij();
ll ans = 1e19;
for(int i = 0;i < w; i++) {
if(dis[2][i] >= K) ans = min(dis[2][i], ans);
else ans = min(ans, dis[2][i] + (K - dis[2][i] + w - 1) / w * w);
}
cout << ans << endl;
for(int i = 1;i <= 4; i++) g[i].clear();
}
}
signed main() {
solve();
}