oj.uz

Submission #938702

# Submission time Handle Problem Language Result Execution time Memory
938702 2024-03-05T12:50:39 Z Alebn Toll (BOI17_toll) C++14
0 / 100
 3000 ms 10956 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));
    }
    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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2730 ms 808 KB Output is correct
8 Execution timed out 3054 ms 1184 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2730 ms 808 KB Output is correct
8 Execution timed out 3054 ms 1184 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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