题目链接

题目描述

给定 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;
}