Lazy Running

Posted on | In , ,

题目链接

同余最短路

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const ll MAX = 1e18;
struct POINT
{
    int dis;
    int id;
} a[10][5];
ll d[5][60050];
void djs(int st, ll m)
{
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(2, 0));

    while (!q.empty())
    {
        P now = q.top();
        q.pop();
        ll dis1 = now.second;
        int u = now.first;

    if(dis1>d[u][dis1%m]) continue;
        for (int i = 0; i < 2; i++)
        {
            ll dis2 = a[u][i].dis + d[u][dis1 % m];
            if (dis2 < d[a[u][i].id][dis2 % m])
            {
                d[a[u][i].id][dis2 % m] = dis2;
                q.push(P(a[u][i].id, dis2));
            }
        }
    }
}
template<class T>
void read(T& ret)
{
    ret = 0;
    char c;
    while ((c = getchar()) > '9' || c < '0');
    while (c <= '9' && c >= '0')
    {
        ret = ret * 10 + c - '0';
        c = getchar();
    }
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        ll k;
        ll ans = MAX;
        int d1, d2, d3, d4;
        read(k), read(d1), read(d2), read(d3), read(d4);
        a[1][0].dis = d1, a[1][0].id = 2;
        a[1][1].dis = d4, a[1][1].id = 4;
        a[2][0].dis = d2, a[2][0].id = 3;
        a[2][1].dis = d1, a[2][1].id = 1;
        a[3][0].dis = d3, a[3][0].id = 4;
        a[3][1].dis = d2, a[3][1].id = 2;
        a[4][0].dis = d4, a[4][0].id = 1;
        a[4][1].dis = d3, a[4][1].id = 3;
        ll m = min(d1, d2) * 2;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j <= m; j++)
                d[i][j] = MAX;
        d[2][0] = 0;
        djs(2, m);
        for (int i = 0; i < m; i++)
        {
            if (d[2][i] < k)
            {
                ll yu = k - d[2][i], cx;
                if (yu % m)
                    cx = (yu / m) + 1;
                else
                    cx = yu / m;
                ans = min(ans, d[2][i] + cx * m);
            }
            else
                ans = min(ans, d[2][i]);
        }
        printf("%lld\n", ans);
    }
}
0%