Submission #836366

#	Time	Username	Problem	Language	Result	Execution time	Memory
836366		lamduybao03	Toll (BOI17_toll)	C++14	100 / 100	222 ms	60016 KiB

toll

#include <bits/stdc++.h>
#define int long long
#define sqr(x) ((x) * (x))
using namespace std;
typedef pair<int, int> pi;
typedef pair<pi, int> ppi;
const int mod = 1e9+7;
const int inv_2 = (mod+1) / 2;


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
    int k, n, m, o;
    cin >> k >> n >> m >> o;
    int p[n+1][k][18];
    int toll[n+1][k][18];
    fill(p[0][0], p[n+1][0], n);
    memset(toll, 0x3f, sizeof(toll));
    for(int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        p[b][a%k][0] = a;
        toll[b][a%k][0] = t;
    }
    for(int x = 1; x < 18; x++) {
        for(int u = 0; u < n; u++) {
            for(int i = 0; i < k; i++) {
                int v = p[u][i][x-1];
                for(int j = 0; j < k; j++) {
                    p[u][j][x] = min(p[u][j][x], p[v][j][x-1]);
                    toll[u][j][x] = min(toll[u][j][x], toll[u][i][x-1] + toll[v][j][x-1]);
                }
            }
        }
    }
    while(o--) {
        int a, b;
        cin >> a >> b;
        int delta = b / k - a / k;
        int dis[k];
        fill(dis, dis+k, 1e18);
        dis[b % k] = 0;
        int id = b / k;
        for(int i = 0; i < 18; i++) {
            if(delta & (1 << i)) {
                int tmp[k];
                fill(tmp, tmp+k, 1e18);
                for(int j = 0; j < k; j++) {
                    for(int x = 0; x < k; x++) {
                        tmp[x] = min(tmp[x], dis[j] + toll[id*k+j][x][i]);
                    }
                }
                id -= (1 << i);
                for(int j = 0; j < k; j++) {
                    dis[j] = tmp[j];
                }
            }
        }
        int ans = dis[a%k];
        if(ans > 1e17)
            cout << "-1\n";
        else {
            cout << ans << "\n";
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44