Submission #938702

#	Time	Username	Problem	Language	Result	Execution time	Memory
938702		Alebn	Toll (BOI17_toll)	C++14	0 / 100	3057 ms	10956 KiB

toll

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Edge {
    int x, y, t;
    Edge(int xi, int yi, int ti):x(xi),y(yi),t(ti){}
};
struct Path {
    int i, c;
    Path(int ii, int ci):i(ii),c(ci){}
};
bool compare(Path a, Path b) {
    return a.c < b.i;
}

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));
    }
    while(q--) {
        // djikstra from a to b
        cin >> x >> y;
        priority_queue<Path, vector<Path>, function<bool(Path, Path)>> pq(compare);
        vector<int> dist(n, LLONG_MAX);
        Path temp(0,0);
        pq.push(Path(x, 0));
        while(pq.size()) {
            temp = pq.top();
            pq.pop();
            if(dist[temp.i] < temp.c) continue;
            dist[temp.i] = temp.c;
            for(auto j : graph[temp.i]) {
                if(temp.c + j.t < dist[j.y]) pq.push(Path(j.y, temp.c + j.t));
            }
        }
        if(dist[y] == LLONG_MAX) cout << "-1\n";
        else cout << dist[y] << "\n";
    }
}

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