| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1072762 | 2024-08-24T04:13:53 Z | ssitaram | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
vector<vector<pair<int, ll>>> 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<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vector<priority_queue<ll>> best2(n);
for (int i = 0; i < k; ++i) {
pq.push({0, p[i]});
best2[p[i]].push(0);
}
while (!pq.empty()) {
pair<ll, int> state = pq.top();
pq.pop();
if (state.first > best2[state.second].top()) continue;
if (!state.second) {
return state.first;
}
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;
}