Submission #938785

#	Time	Username	Problem	Language	Result	Execution time	Memory
938785		vjudge1	Toll (BOI17_toll)	C++17	10 / 100	136 ms	7868 KiB

toll

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second

using namespace std;

struct Edge {
    int x, y, t;
    Edge(int xi, int yi, int ti):x(xi),y(yi),t(ti){}
};

int k, n, m, q, x, y, t;
vector<vector<Edge>> graph;

signed main() {
    cin >> k >> n >> m >> q;
    graph = vector<vector<Edge>>(n);
    for(int i = 0; i < m; i++) {
        cin >> x >> y >> t;
        graph[x].push_back(Edge(x, y, t));
    }
    priority_queue<pair<int,int>> pq;
    vector<int> dist(n, LLONG_MAX);
    pair<int,int> temp;
    pq.push({0, 0});
    while(pq.size()) {
        temp = pq.top();
        pq.pop();
        temp.ff = -temp.ff;
        //cout << temp.ff << " " << temp.ss << "\n";
        if(dist[temp.ss] < temp.ff) continue;
        dist[temp.ss] = temp.ff;
        for(auto j : graph[temp.ss]) {
            if(temp.ff + j.t < dist[j.y]) pq.push({-(temp.ff + j.t), j.y});
        }
    }
    while(q--) {
        cin >> x >> y;
        if(dist[y] == LLONG_MAX) cout << "-1\n";
        else cout << dist[y] << "\n";
    }
}

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