oj.uz

Submission #938781

# Submission time Handle Problem Language Result Execution time Memory
938781 2024-03-05T14:20:57 Z vjudge1 Toll (BOI17_toll) C++17
0 / 100
 94 ms 6480 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 4416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 6480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 4416 KB Output isn't correct
2 Halted 0 ms 0 KB -