제출 #628719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628719		bojackduy	Toll (BOI17_toll)	C++14	0 / 100	36 ms	4548 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;
const int inf = 1e9;
int k, n, m, q;
vii a[N];
pii b[N];
void subtask1() {
        vi d(n + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii> > kew;
        kew.push(pii(0, 0));
        d[0] = 0;
        while (kew.size()) {
            int u = kew.top().se;
            ll du = kew.top().fi;
            kew.pop();
            if (du > d[u]) continue;
            for (pii v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    kew.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 + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> kew;
    kew.push(pii(0, 0));
    d[0] = 0;
    while (kew.size()) {
        int u = kew.top().se;
        int du = kew.top().fi;
        kew.pop();
        if (du > d[u]) continue;
        for (pii v: a[u]) {
            if (d[v.se] > du + v.fi) {
                d[v.se] = du + v.fi;
                kew.push(pii(d[v.se], v.se));
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (d[b[i].se] == inf) {
            cout << -1 << '\n';
        } else cout << 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 + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii>> kew;
        kew.push(pii(0, x));
        d[x] = 0;
        while (kew.size()) {
            int u = kew.top().se;
            int du = kew.top().fi;
            if (u == y) {
                cout << d[u] << '\n';
            break;
            }
            kew.pop();
            if (du > d[u]) continue;
            for (pli v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    kew.push(pii(d[v.se], v.se));
                }
            }
        }
        if (d[y] == inf) 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));
    }
    int cnt = 0;
    for (int i = 1; i <= q; i++) {
        cin >> b[i].fi >> b[i].se;
        if (b[i].fi == 0) cnt++;
    }
    if (k == 1) subtask1(); else
    if (cnt == q) subtask2(); else
    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