Submission #1294559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294559		sunflower	Toll (BOI17_toll)	C++17	10 / 100	39 ms	4500 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)

#define fi first
#define se second
#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

const long long INF = (long long) 1e18 + 7;

#define MAX_NODE 50500
#define MAX_QUERY 10100
int K, numNode, numEdge, numQuery;

vector<pair<int, int>> adj[MAX_NODE + 2];
ll dist[MAX_NODE + 2];

void Dijkstra(int s) {

#define ii pair<long long, int>
    FOR(i, 1, numNode) dist[i] = INF;
    priority_queue<ii, vector<ii>, greater<ii>> q;
    #define PUSH(s) q.push(make_pair(dist[(s)], (s)))

    dist[s] = 0;
    PUSH(s);

    while (!q.empty()) {
        ll d = q.top().fi;
        int u = q.top().se;
        q.pop();

        if (d != dist[u]) continue;

        for (const pair<int, int> &e : adj[u]) {
            int v = e.fi, w = e.se;
            if (minimize(dist[v], dist[u] + w)) PUSH(v);
        }
    }

    FOR(i, 1, numNode) if (dist[i] == INF) dist[i] = -1;
}


int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);

    cin >> K >> numNode >> numEdge >> numQuery;
    FOR(i, 1, numEdge) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }

    Dijkstra(0);

    while (numQuery--) {
        int u, v;
        cin >> u >> v;
        assert(u == 0);
        cout << dist[v] << "\n";
    }

    return 0;
}

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