HDU6071 【Lazy Running】

发表于 | 分类于 ，

$\Large\mathscr{D}\mathcal{escription}$

有一个环，上面有 $1 - 4$ 号点，给出相邻两点之间的距离(无向边)。

小 $Q$ 要从 $2$ 号点出发并回到 $2$ 号点。他可以重复经过一条边，但不会在边上掉头(即会完整地走过一条边)。

现在小 $Q$ 给定你一个整数 $k$，他想知道在经过的路程不小于 $k$ 的情况下，最少需要经过的路程。

$\Large\mathscr{S}\mathcal{olution}$

由于 $k$ 比较大，我们考虑同余最短路。

因为最后要回到原地，所以我们选取 $d1 \times 2$ 和 $d2 \times 2$ 的较小值作为 $Base$ (一来一回)

因为存在掉头的情况，所以不好直接求得回到 $2$ 号点的 $Dis$ 值。

我们考虑用 $Dis_{i,j}$ 表示 从 $2$ 号点到第 $i$ 号点经过的路程 $mod$ $Base$ $=$ $j$ 的最小值。

然后就直接跑最短路就 $OK$ 了。

$\Large\mathscr{C}\mathcal{ode}$

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 6e4 + 7;

int d[5], Base;
long long Dis[5][N];
bool Vis[5][N];

struct Node {
    int id, num;
    long long val;
};
std::priority_queue <Node> Q;
inline bool operator < (Node x, Node y) {
    return x.val > y.val;
}

inline void Dij() {
    memset(Dis, 0x3f, sizeof(Dis));
    memset(Vis, false, sizeof(Vis));
    Dis[2][0] = 0;
    Q.push( (Node) {2, 0, 0});
    while (Q.size()) {
        int u = Q.top().id, num = Q.top().num; long long Val = Q.top().val; Q.pop();
        if (Vis[u][num]) continue;
        Vis[u][num] = true;
        int v = u % 4 + 1, p = (num + d[u]) % Base;
        if (Dis[v][p] > Val + d[u]) {
            Dis[v][p] = Val + d[u];
            Q.push( (Node) {v, p, Dis[v][p]});
        }
        v = (u + 2) % 4 + 1, p = (num + d[v]) % Base;
        if (Dis[v][p] > Val + d[v]) {
            Dis[v][p] = Val + d[v];
            Q.push( (Node) {v, p, Dis[v][p]});
        }
    }
}

int main() {
    int T;
    read(T);
    while (T--) {
        long long k;
        read(k);
        for (int i = 1; i <= 4; ++i) read(d[i]);
        Base = std::min(d[1], d[2]) * 2;
        Dij();
        long long Ans = 1e18 + 1e6;
        for (int i = 0; i < Base; ++i) {
            if (Dis[2][i] >= k) Ans = std::min(Ans, Dis[2][i]);
            else Ans = std::min(Ans, Dis[2][i] + (k - Dis[2][i] + Base - 1) / Base * Base);
        }
        printf("%lld\n", Ans);
    }
    return 0;
}