oj.uz

Submission #938775

# Submission time Handle Problem Language Result Execution time Memory
938775 2024-03-05T14:16:36 Z vjudge1 Toll (BOI17_toll) C++17
0 / 100
 3000 ms 6168 KB 
#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));
    }
    priority_queue<Path, vector<Path>, function<bool(Path, Path)>> pq(compare);
    vector<int> dist(n, LLONG_MAX);
    Path temp(0,0);
    pq.push(Path(0, 0));
    while(pq.size()) {
        temp = pq.top();
        pq.pop();
        //cout << temp.i << " " << temp.c << "\n";
        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));
        }
    }
    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 51 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 6168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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