Submission #681918

#	Time	Username	Problem	Language	Result	Execution time	Memory
681918		Ronin13	Toll (BOI17_toll)	C++14	100 / 100	491 ms	49176 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 5e4 + 1;
int dist[nmax][41][5];
int k;
int get(int a, int b){
    int A = a / k;
    int B = b / k;
    if(A >= B){
        return -1;
    }
    vector <pii> vec;
    vec.pb({a, 0});
    while(B > A + 40){
        vector <pii> nw;
        int d[5];
        fill(d, d + 5, 1e9 + 1);
        for(auto x : vec){
            int v = x.f, D = x.s;
            for(int j = 0; j < k; j++){
                d[j] = min(d[j], dist[v][40][j] + D);
            }
        }
        A += 40;
        vec.clear();
        for(int j = 0; j < k; j++){
            if(d[j] != 1e9 + 1)
                vec.pb({A * k + j, d[j]});
        }
    }
    int ans = 1e9 + 1;
    for(auto x : vec){
        int v = x.f, D = x.s;
        ans = min(ans, dist[v][B - A][b % k] + D);
    }
    if(ans == 1e9 + 1) return -1;
    return ans;
}

int main(){
    int n, m,  o; cin >> k >> n >> m >> o;
    vector <vector <pii> > g(n + 1);
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        int t; cin >> t;
        g[u].pb({v, t});
    }
    for(int i = n - 1; i >= 0; i--){
        for(int j = 0; j <= 40; j++){
            for(int x = 0; x < k; x++)
                dist[i][j][x] = 1e9 + 1;
        }
        for(auto ed : g[i]){
            int to = ed.f, x = ed.s;
            dist[i][1][to % k] = x;
        }
        for(int j = 2; j <= 40; j++){
            for(int x = 0; x < k; x++){
                for(auto ed : g[i]){
                    int to = ed.f;
                    dist[i][j][x] = min(dist[i][j][x], dist[to][j - 1][x] + dist[i][1][to % k]);
                }
            }
        }
    }
    while(o--){
        int a, b; cin >> a >> b;
        cout << get(a, b) << "\n";
    }
    return 0;
}

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