# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
938775 |
2024-03-05T14:16:36 Z |
vjudge1 |
Toll (BOI17_toll) |
C++17 |
|
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";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
51 ms |
3420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3065 ms |
6168 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
51 ms |
3420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |