#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MxN = 100010;
struct state_t {
int v;
ll w;
bool operator < (const state_t &o) const {
return w > o.w;
}
state_t(int _v, ll _w):
v(_v), w(_w) {}
};
vector<pair<int, ll>> adj[MxN];
priority_queue<state_t> pq;
ll dist[MxN][2]; // [0] = best, [1] = secondary
bitset<MxN> visited;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0; i<M; ++i) {
adj[R[i][0]].emplace_back(R[i][1], L[i]);
adj[R[i][1]].emplace_back(R[i][0], L[i]);
}
memset(dist, 0x3f, sizeof dist);
for(int i=0; i<K; ++i) {
pq.emplace(P[i], dist[P[i]][0] = 0ll);
}
while(!pq.empty()) {
state_t now = pq.top(); pq.pop();
if(visited[now.v]) {
continue;
}
visited[now.v] = true;
for(auto x: adj[now.v]) {
ll nxt = now.w + x.second;
if(dist[x.first][1] > nxt) {
dist[x.first][1] = nxt;
if(dist[x.first][1] < dist[x.first][0]) {
swap(dist[x.first][1], dist[x.first][0]);
}
if(dist[x.first][1] <= 1e9 + 100) {
pq.emplace(x.first, dist[x.first][1]);
}
}
}
}
return dist[0][1];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4604 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 12 |
Correct |
6 ms |
4976 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4604 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 12 |
Correct |
6 ms |
4976 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4336 KB |
Output is correct |
| 16 |
Correct |
310 ms |
83804 KB |
Output is correct |
| 17 |
Correct |
54 ms |
17612 KB |
Output is correct |
| 18 |
Correct |
67 ms |
20072 KB |
Output is correct |
| 19 |
Correct |
399 ms |
89168 KB |
Output is correct |
| 20 |
Correct |
218 ms |
69588 KB |
Output is correct |
| 21 |
Correct |
28 ms |
10788 KB |
Output is correct |
| 22 |
Correct |
231 ms |
65228 KB |
Output is correct |
