【HDOJ6071】Lazy Running(同余最短路思想)

72 阅读 0 评论 48 点赞

我是靠谱客的博主曾经电话，这篇文章主要介绍【HDOJ6071】Lazy Running(同余最短路思想)，现在分享给大家，希望可以做个参考。

传送门

题目：
四个点 $1, 2, 3, 4$ 顺序连成环，给定相邻两点间的距离，问从 $2$ 号点出发再回到 $2$ 号点的所有路径中，路径长度不小于 $k$ 的最小值。输出这个最小值。 $1 \leq k \leq 1 e 18$
思路：
主要用到同余的思想。
记 $w=min(dis_{12},dis_{23})$ 对于 $2 \to 2$ 的一条路径，记其路径长度为 $l e n$ ，那么 $l e n + k * 2 w$ ， $(k \geq 0)$ 对应的路径也是一种合法路径，这些合法路径长度根据 $% 2 w$ 的值将其分为 $2 w$ 组，并且求出每个同余类 $i$ 对应的最短的合法路径的长度 $m l e n [i]$ 。
$m l e n [i]$ 表示从 $2 \to 2$ 的合法路径中（路径长度为len），满足 $l e n % (2 w) = i$ 的最小的 $l e n$ 值。
对于每个同余类 $i$ ，如果 $m l e n [i] \geq k$ 那么更新答案，否则，在 $m l e n [i]$ 的基础上累加 $2 w$ ，直至满足长度 $\geq k$ ，再更新答案。
那么怎么获得 $m l e n []$ 数组呢，可以暴搜，也可以用spfa做。
用spfa做的话 $d i s [i] [j]$ 表示从 $2$ 出发到达 $i$ 满足 $% (2 w) = j$ 的最小长度。队列里存上一个点距离当前点的最短距离，初始化存入{ $2, 0$ }。
ac代码：

复制代码

#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 6e4+10;
struct Edge{
int nxt; ll val;
};
struct node{
int now; ll v;
};
vector<Edge> edge[5];
queue<node> q;
int t;
ll d12, d23, d34, d41, w, k, dis[5][maxn];
void spfa()
{
for(int i = 0; i <= 4; i++)
for(int j = 0; j < w; j++)
dis[i][j] = LLONG_MAX;
q.push({2, 0});
while(!q.empty())
{
int now = q.front().now; ll v = q.front().v; q.pop();
for(auto e: edge[now])
{
ll tmp = v+e.val;
if(dis[e.nxt][tmp%w]>tmp)
{
dis[e.nxt][tmp%w] = tmp;
q.push({e.nxt, tmp});
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld %lld %lld %lld", &k, &d12, &d23, &d34, &d41);
w = 2*min(d12, d23);
edge[1].push_back({2, d12}); edge[2].push_back({1, d12});
edge[2].push_back({3, d23}); edge[3].push_back({2, d23});
edge[3].push_back({4, d34}); edge[4].push_back({3, d34});
edge[4].push_back({1, d41}); edge[1].push_back({4, d41});
spfa();
ll ans = LLONG_MAX;
for(int i = 0; i < w; i++)
{
if(dis[2][i]>=k) ans = min(ans, dis[2][i]);
else
{
ll sub = k-dis[2][i];
ll p = sub%w==0 ? sub : (sub/w+1)*w;
ans = min(ans, dis[2][i]+p);
}
}
printf("%lldn", ans);
for(int i = 1; i <= 4; i++) edge[i].clear();
}
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
#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 6e4+10;
struct Edge{
int nxt; ll val;
};
struct node{
int now; ll v;
};
vector<Edge> edge[5];
queue<node> q;
int t;
ll d12, d23, d34, d41, w, k, dis[5][maxn];
void spfa()
{
for(int i = 0; i <= 4; i++)
for(int j = 0; j < w; j++)
dis[i][j] = LLONG_MAX;
q.push({2, 0});
while(!q.empty())
{
int now = q.front().now; ll v = q.front().v; q.pop();
for(auto e: edge[now])
{
ll tmp = v+e.val;
if(dis[e.nxt][tmp%w]>tmp)
{
dis[e.nxt][tmp%w] = tmp;
q.push({e.nxt, tmp});
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld %lld %lld %lld", &k, &d12, &d23, &d34, &d41);
w = 2*min(d12, d23);
edge[1].push_back({2, d12}); edge[2].push_back({1, d12});
edge[2].push_back({3, d23}); edge[3].push_back({2, d23});
edge[3].push_back({4, d34}); edge[4].push_back({3, d34});
edge[4].push_back({1, d41}); edge[1].push_back({4, d41});
spfa();
ll ans = LLONG_MAX;
for(int i = 0; i < w; i++)
{
if(dis[2][i]>=k) ans = min(ans, dis[2][i]);
else
{
ll sub = k-dis[2][i];
ll p = sub%w==0 ? sub : (sub/w+1)*w;
ans = min(ans, dis[2][i]+p);
}
}
printf("%lldn", ans);
for(int i = 1; i <= 4; i++) edge[i].clear();
}
return 0;
}