#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5;
ll inf = 1e12;
vector <pair <int, int>> adj[MAX + 5];
bool endd[MAX + 5];
int travel_plan (int n, int m, int r[][2], int w[], int k, int e[]) {
for (int i = 1; i <= n; i++) {
adj[i].clear();
endd[i] = 0;
}
for (int i = 0; i < m; i++) {
adj[r[i][0] + 1].push_back({r[i][1] + 1, w[i]});
adj[r[i][1] + 1].push_back({r[i][0] + 1, w[i]});
}
ll dist[n + 1][2];
for (int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = inf;
priority_queue <vector <ll>, vector <vector <ll>>, greater <vector <ll>>> pq;
for (int i = 0; i < k; i++) {
e[i]++;
dist[e[i]][0] = dist[e[i]][1] = 0;
pq.push({0, 0, e[i]});
}
while (!pq.empty()) {
auto l = pq.top();
pq.pop();
if (dist[l[2]][0] < l[0]) continue;
if (dist[l[2]][1] < l[1]) continue;
for (auto j : adj[l[2]]) {
bool flag = 1;
if (j.second + l[0] < dist[j.first][1]) {
dist[j.first][0] = dist[j.first][1];
flag = 0;
dist[j.first][1] = j.second + l[0];
} else if (j.second + l[0] < dist[j.first][0]) {
flag = 0;
dist[j.first][0] = j.second + l[0];
}
if (!flag) pq.push({dist[j.first][0], dist[j.first][1], j.first});
}
}
return dist[1][0];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6696 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6696 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 13 |
Correct |
5 ms |
6944 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6696 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 13 |
Correct |
5 ms |
6944 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 16 |
Correct |
361 ms |
69824 KB |
Output is correct |
| 17 |
Correct |
94 ms |
23808 KB |
Output is correct |
| 18 |
Correct |
108 ms |
24764 KB |
Output is correct |
| 19 |
Correct |
566 ms |
83372 KB |
Output is correct |
| 20 |
Correct |
225 ms |
54084 KB |
Output is correct |
| 21 |
Correct |
39 ms |
12460 KB |
Output is correct |
| 22 |
Correct |
264 ms |
49464 KB |
Output is correct |
