Submission #8036592


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int u;
    int v;
    long long c;
    Edge() {}
    Edge(int u, int v, long long c): u(u), v(v), c(c) {}
};

struct PqEle {
    int u;
    int num;
    long long content;
    PqEle() {}
    PqEle(int u, int num, long long content): u(u), num(num), content(content) {}
    bool operator <(const PqEle& o) const {
        return make_pair(num, content) > make_pair(o.num, o.content);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto t0 = clock();
    int n, m;
    long long l;
    cin >> n >> m >> l;
    vector<vector<Edge>> adj_list(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        --a;
        --b;
        if (c <= l) {
            adj_list[a].push_back(Edge(a, b, c));
            adj_list[b].push_back(Edge(b, a, c));
        }
    }
    int q;
    cin >> q;
    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first >> queries[i].second;
        --queries[i].first;
        --queries[i].second;
    }
    auto dijkstra = [&](int start_id) {
        priority_queue<PqEle> pq;
        pq.push(PqEle(start_id, 0, 0LL));
        vector<bool> visited(n, false);
        vector<int> dist(n, -1);
        while (!pq.empty()) {
            auto p = pq.top();
            int node_id = p.u;
            pq.pop();
            if (visited[node_id]) {
                continue;
            }
            dist[node_id] = p.num;
            visited[node_id] = true;
            for (auto& edge : adj_list[node_id]) {
                if (!visited[edge.v]) {
                    if (edge.c + p.content > l) {
                        pq.push(PqEle(edge.v, p.num + 1, edge.c));
                    } else {
                        pq.push(PqEle(edge.v, p.num, edge.c + p.content));
                    }
                }
            }
        }
        return dist;
    };
    vector<vector<int>> dists(n);
    for (int i = 0; i < n; ++i) {
        dists[i] = dijkstra(i);
    }
    for (auto q : queries) {
        cout << dists[q.first][q.second] << "\n";
    }
    cerr << "time used = " << (clock() - t0) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Travel by Car
User Tejs
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2317 Byte
Status
Exec Time 1203 ms
Memory 7400 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02
All 500 / 500 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49
Case Name Status Exec Time Memory
00-sample-00 1 ms 256 KB
00-sample-01 1 ms 256 KB
00-sample-02 1 ms 256 KB
01-handmade-03 19 ms 1664 KB
01-handmade-04 990 ms 7400 KB
01-handmade-05 185 ms 1920 KB
01-handmade-06 21 ms 1664 KB
01-handmade-07 21 ms 1664 KB
02-random-08 4 ms 384 KB
02-random-09 11 ms 384 KB
02-random-10 27 ms 1536 KB
02-random-11 3 ms 384 KB
02-random-12 6 ms 384 KB
02-random-13 25 ms 640 KB
02-random-14 1197 ms 3124 KB
02-random-15 20 ms 1664 KB
02-random-16 19 ms 768 KB
02-random-17 22 ms 1152 KB
02-random-18 9 ms 384 KB
02-random-19 2 ms 256 KB
02-random-20 26 ms 1536 KB
02-random-21 9 ms 512 KB
02-random-22 1 ms 256 KB
02-random-23 256 ms 1636 KB
02-random-24 1129 ms 3276 KB
02-random-25 27 ms 1536 KB
02-random-26 2 ms 256 KB
02-random-27 10 ms 896 KB
02-random-28 573 ms 2472 KB
02-random-29 494 ms 2332 KB
02-random-30 20 ms 1536 KB
02-random-31 4 ms 384 KB
02-random-32 12 ms 768 KB
02-random-33 92 ms 1152 KB
02-random-34 327 ms 1804 KB
02-random-35 26 ms 1664 KB
02-random-36 8 ms 640 KB
02-random-37 21 ms 896 KB
02-random-38 1 ms 256 KB
02-random-39 2 ms 256 KB
02-random-40 26 ms 1536 KB
02-random-41 36 ms 1536 KB
02-random-42 5 ms 512 KB
02-random-43 1203 ms 3248 KB
02-random-44 2 ms 256 KB
02-random-45 21 ms 1664 KB
02-random-46 5 ms 384 KB
02-random-47 22 ms 1280 KB
02-random-48 1 ms 256 KB
02-random-49 59 ms 824 KB