#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
int n = N, m = M, k = K;
vector<pair<int, int>> g[n + 2];
for (int i = 0; i < m; i++) {
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
int vis[n + 2];
memset(vis, 0, sizeof(vis));
priority_queue<pair<ll, int>> pq;
for (int i = 0; i < k; i++) {
vis[P[i]] = 1;
pq.push({0, P[i]});
}
ll ans = 0;
while (pq.size() > 0) {
auto x = pq.top();
pq.pop();
x.first *= -1;
if (vis[x.second] == 0) {
vis[x.second] = 1;
continue;
}
if (vis[x.second] == 2) continue;
if (x.second == 0) {
ans = x.first;
break;
}
vis[x.second] = 2;
for (auto y : g[x.second]) {
if (vis[y.first] == 2) continue;
pq.push({-(x.first + y.second), y.first});
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
448 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
448 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
704 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
5 ms |
1088 KB |
Output is correct |
13 |
Correct |
4 ms |
1236 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
448 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
704 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
5 ms |
1088 KB |
Output is correct |
13 |
Correct |
4 ms |
1236 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
2 ms |
340 KB |
Output is correct |
16 |
Correct |
425 ms |
68372 KB |
Output is correct |
17 |
Correct |
74 ms |
13388 KB |
Output is correct |
18 |
Correct |
78 ms |
14836 KB |
Output is correct |
19 |
Correct |
483 ms |
72220 KB |
Output is correct |
20 |
Correct |
301 ms |
63716 KB |
Output is correct |
21 |
Correct |
35 ms |
5836 KB |
Output is correct |
22 |
Correct |
378 ms |
43980 KB |
Output is correct |