Submission #628663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
628663	2022-08-13T15:04:52 Z	bojackduy	Toll (BOI17_toll)	C++14	Compilation error	0 ms	0 KB

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, inf);
        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++) {
            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';
        }
}
const int inf = 1e9;
void subtask2() {
    vi d(n, inf);
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    heap.push(pii(0, 0));
    d[0] = 0;
    while (heap.size()) {
        int u = heap.top().se;
        int 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] == inf ? -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, inf);
        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] == 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));
    }
    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
*/

Compilation message

toll.cpp: In function 'void subtask1()':
toll.cpp:16:17: error: 'inf' was not declared in this scope; did you mean 'ynf'?
   16 |         vi d(n, inf);
      |                 ^~~
      |                 ynf