#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define t_road pair<int, num>
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define num long long
#define next first
#define cost second
#define ndata vector<num>
#define inf 1e18
#define ni pair<num, int>
#define pq set<ni>
graph roads;
ndata t_max;
ndata t_mix;
pq update_queue;
bool _update (int index, num value) {
if (t_max[index] >= value) {
t_mix[index] = t_max[index];
t_max[index] = value;
} else if (t_mix[index] > value) {
t_mix[index] = value;
} else return false;
return t_mix[index] != inf;
}
void update (int index, num value) {
ni data = { t_mix[index], index };
if (_update(index, value)) {
if (update_queue.find(data) != update_queue.end())
update_queue.erase(data);
update_queue.insert({ t_mix[index], index });
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
roads.resize(N);
t_max.resize(N, inf);
t_mix.resize(N, inf);
for (int iR = 0; iR < M; iR ++) {
int a = R[iR][0];
int b = R[iR][1];
int c = L[iR];
roads[a].push_back({ b, c });
roads[b].push_back({ a, c });
}
for (int i = 0; i < K; i ++) {
update(P[i], 0);
update(P[i], 0);
}
while (update_queue.size() != 0) {
ni position = *update_queue.begin();
update_queue.erase(position);
int current = position.second;
num time = position.first;
if (current == 0) return time;
for (t_road next_road : roads[current]) {
num next_time = next_road.cost + time;
int next_node = next_road.next;
update(next_node, next_time);
}
}
return N;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
448 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
980 KB |
Output is correct |
13 |
Correct |
3 ms |
1084 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
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 |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
448 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
980 KB |
Output is correct |
13 |
Correct |
3 ms |
1084 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
484 ms |
68764 KB |
Output is correct |
17 |
Correct |
68 ms |
17616 KB |
Output is correct |
18 |
Correct |
91 ms |
20096 KB |
Output is correct |
19 |
Correct |
671 ms |
74336 KB |
Output is correct |
20 |
Correct |
260 ms |
58244 KB |
Output is correct |
21 |
Correct |
38 ms |
8128 KB |
Output is correct |
22 |
Correct |
286 ms |
53724 KB |
Output is correct |