Submission #1052809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052809		gyg	Toll (BOI17_toll)	C++17	56 / 100	3077 ms	109564 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e4 + 5, SQRT = 1e2, INF = 1e9;

int k, n, m, q;
array<vector<pii>, MAX_N> adj;

unordered_map<int, int> dist;
unordered_set<int> seen;
priority_queue<pii, vector<pii>, greater<pii>> order;
void dijk(int s, bool halt = false) {
    dist.clear(), seen.clear();
    dist[s] = 0, order.push({0, s});
    while (order.size()) {
        int u = order.top().second;
        order.pop();
        if (halt && (u / k) % SQRT == 0) continue;

        if (seen.count(u)) continue;
        seen.insert(u);

        for (pii x : adj[u]) {
            int new_dist = dist[u] + x.second;
            if (dist.count(x.first) && new_dist >= dist[x.first]) continue;
            dist[x.first] = new_dist;
            order.push({new_dist, x.first});
        }
    }
}

unordered_map<int, array<int, MAX_N>> sp;
void precomp() {
    for (int u = 0; u < n; u++) {
        if ((u / k) % SQRT != 0) continue;
        dijk(u);
        for (int v = 0; v < n; v++)
            sp[u][v] = (dist.count(v)) ? dist[v] : INF;
    }
}

int comp(int s, int f) {
    dijk(s, true);
    
    int ans = INF;
    if (dist.count(f)) ans = min(ans, dist[f]);
    for (pii x : dist)
        if ((x.first / k) % SQRT == 0)
            ans = min(ans, x.second + sp[x.first][f]);

    return ans;
}

int main() {
    // freopen("toll.in", "r", stdin);
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    precomp();

    for (int i = 1; i <= q; i++) {
        int s, f; cin >> s >> f;
        int ans = comp(s, f);
        cout << ((ans >= INF) ? -1 : ans) << '\n';
    }
}

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