HDU 6071 Lazy Running(同余最短路)
文章目录
题目描述
给定 4 个点的环,求从 2 出发回到 2 的最短的长度至少为 K 的路径长度。
$K \le 10^{18}$
$d \le 3 \times 10^4$
简要做法
取 $w = min(d_{1,2}, d_{2,3})$,那么对于每一种方案,均可以通过往返跑 $w$ 这条边使得距离增加 $2w$
也就是说,如果存在距离为 $k$ 的方案,那么必然存在距离为 $k + 2w$ 的方案
设 $dis_{i,j}$ 表示从起点出发到达 $i$,距离模 $2w$ 为 $j$ 时的最短路
根据 $dis_{2,j}$ 解不等式即可得到最优路线
时间复杂度 $O(w log w)$
参考代码
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <queue>
#define int long long
const int N = 8 + 5;
const int K = 6e4 + 5;
int k;
int d[N], dis[N][K];
int head[N], num_edge;
struct Node
{
int next, to, dis;
} edge[N];
struct node
{
int cur, r, dis;
bool friend operator<(node a, node b) { return a.dis > b.dis; }
};
void add_edge(int u, int v, int dis)
{
edge[++num_edge] = Node{head[u], v, dis}, head[u] = num_edge;
}
int read()
{
int x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
void dijkstra()
{
int w = 2 * std::min(d[1], d[2]);
memset(dis, 0x3f, sizeof dis);
std::priority_queue<node> Q;
Q.push(node{2, 0, 0});
dis[2][0] = 0;
while (!Q.empty())
{
node now = Q.top();
Q.pop();
int u = now.cur, r = now.r;
if (now.dis > dis[u][r] or now.dis >= k + w)
continue;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to, nr = (r + edge[i].dis) % w;
if (dis[v][nr] > dis[u][r] + edge[i].dis)
{
dis[v][nr] = dis[u][r] + edge[i].dis;
Q.push(node{v, nr, dis[v][nr]});
}
}
}
int kmod = k % w, diff = w;
for (int i = 0; i < w; ++i)
if (dis[2][i] <= k)
{
if (i >= kmod)
diff = std::min(diff, i - kmod);
else
diff = std::min(diff, w - (kmod - i));
}
else
diff = std::min(diff, dis[2][i] - k);
printf("%lld\n", k + diff);
}
signed main()
{
for (int T = read(); T--; dijkstra())
{
k = read(), num_edge = 0;
memset(edge, 0, sizeof edge);
memset(head, 0, sizeof head);
for (int i = 1; i <= 4; i++)
d[i] = read();
for (int i = 1; i <= 4; i++)
add_edge(i, i % 4 + 1, d[i]), add_edge(i % 4 + 1, i, d[i]);
}
return 0;
}