| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072753 | 2024-08-24T04:05:19 Z | ssitaram | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n, m, k; cin >> n >> m >> k;
vector<vector<pair<int, int>>> adj(n);
while (m--) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vector<priority_queue<ll>> best2(n);
while (k--) {
int v; cin >> v;
pq.push({0, v});
best2[v].push(0);
}
while (!pq.empty()) {
pair<ll, int> state = pq.top();
pq.pop();
if (state.first > best2[state.second].top()) continue;
if (!state.second) {
cout << state.first << '\n';
return 0;
}
for (pair<int, int>& edge : adj[state.second]) {
if (best2[edge.first].size() < 2) {
best2[edge.first].push(state.first + edge.second);
if (best2[edge.first].size() == 2) pq.push({best2[edge.first].top(), edge.first});
} else if (state.first + edge.second < best2[edge.first].top()) {
best2[edge.first].pop();
best2[edge.first].push(state.first + edge.second);
pq.push({best2[edge.first].top(), edge.first});
}
}
}
return 0;
}