HDU 6071 Lazy Running（同余最短路的应用）

110 阅读 0 评论 73 点赞

我是靠谱客的博主平常大米，这篇文章主要介绍HDU 6071 Lazy Running（同余最短路的应用），现在分享给大家，希望可以做个参考。

Lazy Running

思路

还是利用同余的思想，假设存在一条长度为 $k$ 的路，那么也一定存在一条 $k + b a s e$ 的路 $b a s e = 2 * m i n (d 1, d 2)$ 。

$d i s [i] [j] = x$ 表示的是，从 $2 - > i$ 点 $x \equiv j (m o d b a s e)$ 的满足条件的最小的 $x$ ，所以我们只要求出所有的 $d i s [2] [i]$ ，再通过同余的性质去得到我们的最短路的花费，对于 $d i s [2] [i] > k$ 我们取 $m i n (a n s, d i s [2] [i])$ ，否则的话，我们取 $m i n (a n s, d i s [2] [i] + (k - d i s [2] [i] + m i d - 1) / m o d * m o d)$ ，之后我们就可以得到我们的正确解了

代码

复制代码

/*
Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl 'n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
void print(ll x) {
if(x < 10) {
putchar(x + 48);
return ;
}
print(x / 10);
putchar(x % 10 + 48);
}
const int N = 6e4 + 10;
ll dis[5][N], k, d1, d2, d3, d4, mod;
vector< pair< int, ll > > G[5];
void Dijkstra() {
priority_queue< pair< ll, int >, vector< pair< ll, int > >, greater< pair< ll, int > > > q;
q.push(mp(0, 2));
memset(dis, 0x3f, sizeof dis);
dis[2][0] = 0;
while(q.size()) {
auto temp = q.top();
q.pop();
if(temp.first > dis[temp.second][temp.first % mod]) continue;
for(auto i : G[temp.second]) {
int to = i.first;
ll w = i.second + temp.first;
if(dis[to][w % mod] > w) {
dis[to][w % mod] = w;
q.push(mp(w, to));
}
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = read();
while(t--) {
k = read(), d1 = read(), d2 = read(), d3 = read(), d4 = read();
mod = min(d1, d2) * 2;
for(int i = 1; i <= 4; i++) G[i].clear();
G[1].pb(mp(2, d1)), G[1].pb(mp(4, d4));
G[2].pb(mp(3, d2)), G[2].pb(mp(1, d1));
G[3].pb(mp(2, d2)), G[3].pb(mp(4, d3));
G[4].pb(mp(3, d3)), G[4].pb(mp(1, d4));
Dijkstra();
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 0; i < mod; i++) {
if(k < dis[2][i]) ans = min(ans, dis[2][i]);
else {
ans = min(ans, dis[2][i] + (k - dis[2][i] + mod - 1) / mod * mod);
}
}
printf("%lldn", ans);
}
return 0;
}

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
/*
Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl 'n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
void print(ll x) {
if(x < 10) {
putchar(x + 48);
return ;
}
print(x / 10);
putchar(x % 10 + 48);
}
const int N = 6e4 + 10;
ll dis[5][N], k, d1, d2, d3, d4, mod;
vector< pair< int, ll > > G[5];
void Dijkstra() {
priority_queue< pair< ll, int >, vector< pair< ll, int > >, greater< pair< ll, int > > > q;
q.push(mp(0, 2));
memset(dis, 0x3f, sizeof dis);
dis[2][0] = 0;
while(q.size()) {
auto temp = q.top();
q.pop();
if(temp.first > dis[temp.second][temp.first % mod]) continue;
for(auto i : G[temp.second]) {
int to = i.first;
ll w = i.second + temp.first;
if(dis[to][w % mod] > w) {
dis[to][w % mod] = w;
q.push(mp(w, to));
}
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = read();
while(t--) {
k = read(), d1 = read(), d2 = read(), d3 = read(), d4 = read();
mod = min(d1, d2) * 2;
for(int i = 1; i <= 4; i++) G[i].clear();
G[1].pb(mp(2, d1)), G[1].pb(mp(4, d4));
G[2].pb(mp(3, d2)), G[2].pb(mp(1, d1));
G[3].pb(mp(2, d2)), G[3].pb(mp(4, d3));
G[4].pb(mp(3, d3)), G[4].pb(mp(1, d4));
Dijkstra();
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 0; i < mod; i++) {
if(k < dis[2][i]) ans = min(ans, dis[2][i]);
else {
ans = min(ans, dis[2][i] + (k - dis[2][i] + mod - 1) / mod * mod);
}
}
printf("%lldn", ans);
}
return 0;
}