#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
priority_queue<pair<int, int>> pq;
vector<int> b(N, 1e9+7), sb(N, 1e9+7);
for (int i = 0; i < K; i++) {
pq.push({0, P[i]});
b[P[i]] = 0; sb[P[i]] = 0;
}
vector<bool> v(N, 0);
while (!pq.empty()) {
int a = pq.top().second; pq.pop();
if (v[a]) continue;
if (sb[a] < 1e9+7) v[a] = 1;
else continue;
for (pair<int, int> i : adj[a]) {
if (b[i.first] > sb[a]+i.second) {
sb[i.first] = b[i.first];
b[i.first] = sb[a]+i.second;
if (sb[i.first] < 1e9+7) pq.push({-sb[i.first], i.first});
}
else if (sb[i.first] > sb[a] + i.second) {
sb[i.first] = sb[a]+i.second;
pq.push({-sb[i.first], i.first});
}
}
}
return sb[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |