Submission #628657

#	Time	Username	Problem	Language	Result	Execution time	Memory
628657		bojackduy	Toll (BOI17_toll)	C++14	0 / 100	30 ms	4564 KiB

toll

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int N = 1e5 + 1;
int k, n, m, q;
vii a[N];
pii b[N];
void subtask1() {
        vi d(n, 1e9);
        priority_queue<pii, vector<pii>, greater<pii> > heap;
        heap.push(pii(0ll, 0));
        d[0] = 0;
        while (heap.size()) {
            int u = heap.top().se;
            ll du = heap.top().fi;
            heap.pop();
            if (du > d[u]) continue;
            for (pii v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    heap.push(pii(d[v.se], v.se));
                }
            }
        }
        for (int i = 1; i <= q; i++) {
            int x, y;
            x = b[i].fi;
            y = b[i].se;
            if (x > y) {
                cout << "-1\n";
                continue;
            }
            cout << d[y] - (x <= 0 ? 0 : d[x - 1]) << '\n';
        }
}
void subtask2() {
    vi d(n, 1e9);
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    heap.push(pii(0, 0));
    d[0] = 0;
    while (heap.size()) {
        int u = heap.top().se;
        ll du = heap.top().fi;
        heap.pop();
        if (du > d[u]) continue;
        for (pii v: a[u]) {
            if (d[v.se] > du + v.fi) {
                d[v.se] = du + v.fi;
                heap.push(pii(d[v.se], v.se));
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << (d[b[i].se] == 1e9 ? -1 : d[b[i].se]) << '\n';
    }
}
void subtask3() {
    for (int i = 1; i <= q; i++) {
        int x, y;
        x = b[i].fi;
        y = b[i].se;
        vi d(n, 1e9);
        priority_queue<pii, vector<pii>, greater<pii> > heap;
        heap.push(pii(0, x));
        d[x] = 0;
        while (heap.size()) {
            int u = heap.top().se;
            int du = heap.top().fi;
            if (u == y) {
                cout << d[u] << '\n';
            break;
            }
            heap.pop();
            if (du > d[u]) continue;
            for (pli v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    heap.push(pii(d[v.se], v.se));
                }
            }
        }
        if (d[y] == 1e9) cout << "-1\n";
    }
}
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x].pb(pii(z, y));
    }
    bool flag = 1;
    for (int i = 1; i <= q; i++) {
        cin >> b[i].fi >> b[i].se;
        if (b[i].fi) flag = 0;
    }
    if (k == 1) {
        subtask1();
    return 0;
    }
    if (flag) {
        subtask2();
    return 0;
    }
    subtask3();
    return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/

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