#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<ll> dist(n, INF), fin(n, INF);
priority_queue<pll> pq;
for (int i = 0; i < k; i++) {
pq.push({0, p[i]});
dist[p[i]] = 0;
}
while (!pq.empty()) {
auto N = pq.top(); pq.pop();
ll t = -N.f, u = N.s;
if (dist[u] != t) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
fin[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto N = pq.top(); pq.pop();
ll t = -N.f, u = N.s;
if (fin[u] != t) continue;
vector<vector<ll>> pos;
for (auto [v, w] : adj[u]) {
pos.pb({w + dist[v], v, w});
}
sort(all(pos), [&](auto& x, auto& y) {
return x[0] < y[0];
});
for (int i = 1; i < sz(pos); i++) {
ll v = pos[i][1], w = pos[i][2];
if (t + w < fin[v]) {
fin[v] = t + w;
pq.push({-fin[v], v});
}
}
}
ll res = 2e9;
for (int i = 0; i < k; i++) {
smin(res, fin[p[i]]);
}
return (int) res;
}
| # |
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 |
- |
