| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1362112 | hieuminh | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define forr(i, a, b) for (int i = a; i <= b; i++)
#define rfor(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 1e5 + 5;
int N, M, K, R[maxn][2], L[maxn];
ll d1[maxn], d2[maxn];
struct s {
int id;
ll dist;
bool operator<(const s &o) const {
return dist > o.dist;
}
};
vector<s> adj[maxn];
priority_queue<s> pq;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M >> K;
forr(i, 0, N - 1) d1[i] = d2[i] = 1e18;
forr(i, 1, M) cin >> R[i][0] >> R[i][1];
forr(i, 1, M) cin >> L[i];
forr(i, 1, K) {
int P;
cin >> P;
pq.push({P, 0});
d1[P] = d2[P] = 0;
}
forr(i, 1, M) {
int u = R[i][0], v = R[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
while (!pq.empty()) {
ll u = pq.top().id, dist = pq.top().dist;
pq.pop();
if (dist > d2[u])
continue;
for (auto &[v, w] : adj[u]) {
if (d2[u] + w < d1[v]) {
d2[v] = d1[v];
d1[v] = d2[u] + v;
pq.push({v, d2[v]});
} else if (d2[u] + w < d2[v]) {
d2[v] = d2[u] + w;
pq.push({v, d2[v]});
}
}
}
cout << d2[0];
}