# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
601494 |
2022-07-22T05:52:19 Z |
narvalo |
Ferries (NOI13_ferries) |
C++17 |
|
279 ms |
28500 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = (int)1e18;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , m;
cin >> n >> m;
vector<vector<pair<int , int>>> adj(n) , rev(n);
vector<vector<int>> edges(n);
for (int i = 0 ; i < m ; i += 1) {
int a , b , c;
cin >> a >> b >> c;
a -= 1 , b -= 1;
edges[a].push_back(c);
adj[a].emplace_back(b , c);
rev[b].emplace_back(a , c);
}
for (int i = 0 ; i < n ; i += 1) {
sort(edges[i].begin() , edges[i].end());
}
#define pi pair<int , int>
priority_queue<pi , vector<pi> , greater<pi>> pq;
vector<int> d(n , INF);
d[n - 1] = 0;
pq.emplace(d[n - 1] , n - 1);
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
if (d[t.second] != t.first) continue;
for (int i = 0 ; i < (int)rev[t.second].size() ; i += 1) {
auto node = rev[t.second][i];
if (d[node.first] > t.first + edges[node.first].back()) {
d[node.first] = t.first + edges[node.first].back();
pq.emplace(d[node.first] , node.first);
edges[node.first].pop_back();
}
}
}
cout << d[0] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
3156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
279 ms |
28500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |