#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5+7;
const int INF = (int)1e9+7;
vector<pair<int, int> > g[N];
int n, m;
int d1[N], d2[N];
int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
n = _N;
m = _M;
for(int i = 0; i < m; ++i) {
int u = _R[i][0], v = _R[i][1], w = _L[i];
u++;
v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 1; i <= n; ++i) {
d1[i] = d2[i] = INF;
}
priority_queue<pair<int, int> > q;
for(int i = 0; i < _K; ++i) {
int v = _P[i]+1;
d1[v]=d2[v]=0;
q.push({0, v});
}
while(!q.empty()) {
int v = q.top().second;
long long cur_d = -q.top().first;
q.pop();
if(cur_d>d2[v]) {
continue;
}
for(auto [to, w] : g[v]) {
if(d2[v]+w<d1[to]) {
if(d1[to]<d2[to]) {
d2[to]=d1[to];
q.push({-d2[to], to});
}
d1[to]=d2[v]+w;
} else {
if(d2[v]+w<d2[to]) {
d2[to]=d2[v]+w;
q.push({-d2[to], to});
}
}
}
}
return d2[1];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6664 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6664 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6964 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7000 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6664 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6964 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7000 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
297 ms |
61592 KB |
Output is correct |
| 17 |
Correct |
53 ms |
16724 KB |
Output is correct |
| 18 |
Correct |
65 ms |
18000 KB |
Output is correct |
| 19 |
Correct |
388 ms |
64784 KB |
Output is correct |
| 20 |
Correct |
218 ms |
53844 KB |
Output is correct |
| 21 |
Correct |
32 ms |
10324 KB |
Output is correct |
| 22 |
Correct |
244 ms |
51504 KB |
Output is correct |
