| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1072753 | ssitaram | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}