#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first
#define s second
int travel_plan(int N, int M, int R[][2],
int L[], int k, int p[]) {
const ll INF = 1e18;
int n = N, m = M;
vector<vector<pii>> adj(n);
for (int i = 0; i < m; i++) {
int x = R[i][0], y = R[i][1],
w = L[i];
adj[x].pb({y, w});
adj[y].pb({x, w});
}
vector<vector<ll>> dist(2,
vector<ll>(n, INF));
priority_queue<pll> pq;
for (int i = 0; i < k; i++) {
pq.push({0, p[i]});
dist[0][p[i]] = 0;
dist[1][p[i]] = 0;
}
while (!pq.empty()) {
auto N = pq.top(); pq.pop();
ll u = N.s, t = -N.f;
/**
* Propogate every time there
* is a new best second best
* for a node.
*/
for (auto [v, w] : adj[u]) {
if (dist[1][u] + w < dist[0][v]) {
if (dist[0][v] != dist[1][v]) {
pq.push({-dist[0][v], v});
}
swap(dist[0][v], dist[1][v]);
dist[0][v] = dist[1][u] + w;
} else if (dist[1][u] + w < dist[1][v]) {
dist[1][v] = dist[1][u] + w;
pq.push({-dist[1][v], v});
}
}
}
return (int) dist[1][0];
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for (auto [v, w] : adj[u]) {
| ^
crocodile.cpp:36:21: warning: unused variable 't' [-Wunused-variable]
36 | ll u = N.s, t = -N.f;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
