HDU6071 Lazy Running 同余最短路

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意

一张图上有4个点，一开始在点2处 ，最终也回到点2处 ，问我们怎样走，使得总路径和大于等于K并且最小。输出最短路径值。

思路

同余思想： 令$w=min(dis_{12},dis_{23})$，取$min$是为了降低时空复杂度，代码里会看到。 w存在的意义就是可以一直在点2和点1或3之间无止境往返。 假设存在一条合法路径2->2，该路径长度为$len$，则$len+n*2w$也是一条合法路径。而我们要找的就是最短路径。这些个路径会被$\%2w$分成$2w$组，求出每一组同余类$i$的合法路径长度，最后$ans$取$min$。

Dijkstra的过程中： dis[i][j]表示2到i的路径中\%w为j的最小值，所以要求出所有的dis[2][i]。

更新答案： 若dis[2][i]>=k，则ans=min(ans, dis[2][i]) 若dis[2][i]<k，则ans=min(ans, dis[2][i]+若干2w)

Code(62MS)

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
##include "bits/stdc++.h"
using namespace std;

typedef unsigned long long ll;

const int N = 1e6 + 10;
struct edge {
    int v; ll w;
};

struct node {
    int now; ll d;
    bool operator < (const node& rhs) const {
        return d > rhs.d;
    }
};

vector<edge> g[5];
ll dis[5][N], w;

void Dij() {
    for(int i = 1;i <= 4; i++) {
        for(int j = 0;j < w; j++) {
            dis[i][j] = 1e18;
        }
    }
    dis[2][0] = 0;
    priority_queue<node> q;
    q.push({2, 0});
    while(!q.empty()) {
        node p = q.top(); q.pop();
        int u = p.now;
        if(dis[u][p.d % w] < p.d) continue;
        for(auto e : g[u]) {
            int v = e.v;
            ll len = e.w + p.d;
            if(dis[v][len % w] > len) {
                dis[v][len % w] = len;
                q.push({v, len});
            }
        }
    }
}

void solve() {
    int _; cin >> _;
    while(_--) {
        ll d12, d23, d34, d41, K;
        cin >> K >> d12 >> d23 >> d34 >> d41;
        g[1].emplace_back(edge{2, d12});g[2].emplace_back(edge{1, d12});
        g[2].emplace_back(edge{3, d23});g[3].emplace_back(edge{2, d23});
        g[3].emplace_back(edge{4, d34});g[4].emplace_back(edge{3, d34});
        g[4].emplace_back(edge{1, d41});g[1].emplace_back(edge{4, d41});
        w = 2 * min(d12, d23);
        Dij();
        ll ans = 1e19;
        for(int i = 0;i < w; i++) {
            if(dis[2][i] >= K) ans = min(dis[2][i], ans);
            else ans = min(ans, dis[2][i] + (K - dis[2][i] + w - 1) / w * w);
        }
        cout << ans << endl;
        for(int i = 1;i <= 4; i++) g[i].clear();
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/18/hdu6071/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！