#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int edges[][2], int weights[], int exitCount, int exits[]){
#define ll long long
ll incoming[n];
multiset<ll> dist[n];
memset(incoming, 0, sizeof(incoming));
for (ll x = 0; x < n; x++) dist[x].insert(INT_MAX/2),dist[x].insert(INT_MAX/2);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; //for those who have fulfilled the incoming >= 2 req
#define distUpdate(k, newval) dist[k].insert(newval); dist[k].erase(prev(dist[k].end()))
for (ll x = 0; x < exitCount; x++){
distUpdate(exits[x], 0);
distUpdate(exits[x], 0);
pq.push({0, exits[x]});
}
vector<pair<ll, ll>> adjList[n];
for (ll x = 0; x < m; x++){
adjList[edges[x][0]].push_back({edges[x][1], weights[x]});
adjList[edges[x][1]].push_back({edges[x][0], weights[x]});
}
while (!pq.empty()){
ll d = pq.top().first, node = pq.top().second;
pq.pop();
//cout << node << ' ' << d << '\n';
if (d > *prev(dist[node].end())) continue;
for (auto x : adjList[node]){
//cout << x.first << "upd\n";
ll prevSecond = *prev(dist[x.first].end());
if ( d + x.second < prevSecond){ //i.e. distUpdate was successful
incoming[x.first]++;
distUpdate(x.first, d + x.second);
if (incoming[x.first] >= 2) pq.push({*prev(dist[x.first].end()), x.first});
}
}
}
return *prev(dist[0].end());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
2 ms |
776 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
3 ms |
980 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
2 ms |
776 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
3 ms |
980 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
480 KB |
Output is correct |
| 16 |
Correct |
364 ms |
70848 KB |
Output is correct |
| 17 |
Correct |
77 ms |
27724 KB |
Output is correct |
| 18 |
Correct |
106 ms |
30100 KB |
Output is correct |
| 19 |
Correct |
594 ms |
86300 KB |
Output is correct |
| 20 |
Correct |
233 ms |
53008 KB |
Output is correct |
| 21 |
Correct |
35 ms |
10700 KB |
Output is correct |
| 22 |
Incorrect |
266 ms |
52336 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
