# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
601474 |
2022-07-22T05:23:01 Z |
narvalo |
Ferries (NOI13_ferries) |
C++17 |
|
1000 ms |
27432 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
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);
for (int i = 0 ; i < m ; i += 1) {
int a , b , c;
cin >> a >> b >> c;
a -= 1 , b -= 1;
adj[a].emplace_back(b , c);
rev[b].emplace_back(a , c);
}
#define pi pair<int , int>
priority_queue<pi , vector<pi> , greater<pi>> pq;
const int INF = (int)1e18;
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];
vector<int> c1;
vector<pair<int , int>> c2;
for (auto x : adj[node.first]) {
c1.push_back(x.second);
c2.emplace_back(d[x.first] , x.first);
}
sort(c1.begin() , c1.end());
sort(c2.begin() , c2.end());
for (int j = 0 ; j < (int)c1.size() ; j++) {
int new_id = (int)c1.size() - j - 1;
int id = c2[new_id].second;
if (id == t.second) {
if (d[node.first] > t.first + c1[j]) {
d[node.first] = t.first + c1[j];
pq.emplace(d[node.first] , node.first);
}
break;
}
else continue;
}
}
}
cout << d[0] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
75 ms |
528 KB |
Output is correct |
3 |
Execution timed out |
1082 ms |
2792 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
8 ms |
464 KB |
Output is correct |
3 |
Execution timed out |
1086 ms |
2720 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2868 KB |
Output is correct |
2 |
Correct |
20 ms |
2892 KB |
Output is correct |
3 |
Correct |
274 ms |
26312 KB |
Output is correct |
4 |
Correct |
357 ms |
26604 KB |
Output is correct |
5 |
Correct |
313 ms |
25900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
301 ms |
26356 KB |
Output is correct |
2 |
Correct |
316 ms |
26316 KB |
Output is correct |
3 |
Correct |
368 ms |
27404 KB |
Output is correct |
4 |
Correct |
343 ms |
27432 KB |
Output is correct |
5 |
Correct |
401 ms |
27396 KB |
Output is correct |