#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
const ll inf = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<pli> adj[N];
for (int i = 0; i < M; ++i) {
adj[R[i][0]].emplace_back(L[i], R[i][1]);
adj[R[i][1]].emplace_back(L[i], R[i][0]);
// cout << "edge " << R[i][0] << " - " << R[i][1] << " with weight " << L[i] << "\n";
}
priority_queue<pli, vector<pli>, greater<pli>> pq;
bool vis[N];
ll d1[N], d2[N];
for (int i = 0; i < N; ++i) {
vis[i] = false;
d1[i] = d2[i] = inf;
}
for (int i = 0; i < K; ++i) {
int s = P[i];
// cout<<"source "<<s<<"\n";
d1[s] = d2[s] = 0;
pq.emplace(0, s);
}
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
// cout<<"u="<<u<<" d1="<<d1[u]<<" d2="<<d2[u]<<"\n";
for (pli to : adj[u]) {
int v = to.second;
ll alt = d2[u] + to.first;
// cout<<" v="<<v<<" w="<<to.first<<" alt="<<alt<<"\n";
if (d1[v] == d2[v]) {
if (alt < d1[v]) {
d1[v] = alt;
pq.emplace(d2[v], v); // might be inf, but that's fine
// cout<<" first case\n";
}
} else {
// d1[v] < d2[v]
if (alt <= d1[v]) {
d2[v] = d1[v];
d1[v] = alt;
pq.emplace(d2[v], v);
// cout<<" second case\n";
} else if (alt < d2[v]) {
d2[v] = alt;
pq.emplace(d2[v], v);
// cout<<" third case\n";
}
}
}
}
return d2[0];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
448 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
448 KB |
Output is correct |
| 9 |
Correct |
3 ms |
716 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
2 ms |
460 KB |
Output is correct |
| 12 |
Correct |
6 ms |
972 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
448 KB |
Output is correct |
| 9 |
Correct |
3 ms |
716 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
2 ms |
460 KB |
Output is correct |
| 12 |
Correct |
6 ms |
972 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
563 ms |
67672 KB |
Output is correct |
| 17 |
Correct |
104 ms |
16812 KB |
Output is correct |
| 18 |
Correct |
140 ms |
19084 KB |
Output is correct |
| 19 |
Correct |
705 ms |
77352 KB |
Output is correct |
| 20 |
Correct |
326 ms |
52976 KB |
Output is correct |
| 21 |
Correct |
48 ms |
7556 KB |
Output is correct |
| 22 |
Correct |
345 ms |
48944 KB |
Output is correct |
