| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1327034 | riafhasan2010 | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e17;
ll travel_plan(int n, int m, int R[][2], int L[], int k, int p[]) {
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
vector<ll> best(n, inf), second_best(n, inf);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
for (int i = 0; i < k; i++) {
best[p[i]] = 0;
pq.push({0, p[i]});
}
while (!pq.empty()) {
auto [c, u] = pq.top(); pq.pop();
if (c > second_best[u]) continue;
for (auto [v, w] : g[u]) {
if (c + w < best[v]) {
second_best[v] = best[v];
best[v] = c + w;
pq.push({best[v], v});
}
else if (c + w < second_best[v]) {
second_best[v] = c + w;
pq.push({c + w, v});
}
}
}
return second_best[0];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
}
