LOJ539 - 「LibreOJ NOIP Round #1」旅游路线

2017/11/06

题面

链接

做法

这题做法真心妙。

我们先搞一个倍增 Floyd 预处理出两点之间走 2^k 条边的最长路。

然后每次加油枚举下一个加油位置,转移过去。

最后二分答案来得到一个最小的花费使得走的长度超过给定值。

代码

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_M = 107;
const int MAX_S = 30;
int F[MAX_M][MAX_M*MAX_M];
int L[MAX_M][MAX_M];
int dis[MAX_S+1][MAX_M][MAX_M];
int p[MAX_M], c[MAX_M], now[MAX_M];
int N, M, MR, C, T;

void calc() {
    for(int i=1;i<=MAX_S;i++) {
        for(int u=1;u<=N;u++) {
            for(int v=1;v<=N;v++) {
                for(int k=1;k<=N;k++)
                    dis[i][u][v] = max(dis[i][u][v],
                            dis[i-1][u][k] + dis[i-1][k][v]);
            }
        }
    }

    memset(L, -63, sizeof(L));

    for(int i=1;i<=N;i++) L[i][i] = 0;
    for(int u=1;u<=N;u++) {
        int step = c[u];
        for(int i=0;i<=MAX_S;i++) {
            if(step & (1<<i)) {
                memset(now, -63, sizeof(now));
                for(int v=1;v<=N;v++) {
                    for(int k=1;k<=N;k++)
                        now[v] = max(now[v], L[u][k] + dis[i][k][v]);
                }
                memcpy(L[u], now, sizeof(now));
            }
        }
    }

    memset(F, -63, sizeof(F));
    for(int q=0;q<=N*N;q++) {
        for(int u=1;u<=N;u++) {
            if(p[u] > q) {
                F[u][q] = 0;
                continue;
            }
            for(int v=1;v<=N;v++) {
                F[u][q] = max(F[u][q], F[v][q - p[u]] + L[u][v]);
            }
        }
    }
}

int main() {
    scanf("%d %d %d %d", &N, &M, &C, &T);

    for(int i=1;i<=N;i++)
        scanf("%d %d", &p[i], &c[i]), c[i] = min(C, c[i]);

    memset(dis, -63, sizeof(dis));
    for(int i=1;i<=N;i++)
        dis[0][i][i] = 0;

    for(int i=1,u,v,w;i<=M;i++) {
        scanf("%d %d %d", &u, &v, &w);
        dis[0][u][v] = max(dis[0][u][v], w);
    }

    calc();

    while(T--) {
        int s, q, d; scanf("%d %d %d", &s, &q, &d);
        int l = 0, r = q, res = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(F[s][mid] >= d) {
                res = q - mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        printf("%d\n", res);
    }
}