oj.uz

Submission #628657

# Submission time Handle Problem Language Result Execution time Memory
628657 2022-08-13T14:57:54 Z bojackduy Toll (BOI17_toll) C++14
0 / 100
 30 ms 4564 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4468 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4564 KB Output isn't correct
2 Halted 0 ms 0 KB -