| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289115 | harryleee | 악어의 지하 도시 (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
struct cmp{
bool operator()(const pair<int, long long>& a, const pair<int, long long>& b) const {
return a.second > b.second;
}
};
long long travel_plan(int n, int m, int R[][2], long long L[], int k, int P[]){
vector<vector<pair<int, int>>> adj(n);
vector<pair<long long, long long>> dis(n);
for (int i = 0; i < n; ++i) dis[i].first = dis[i].second = inf;
for (int i = 0; i < m; ++i){
int u = R[i][0], v = R[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
priority_queue<pair<int, long long>, vector<pair<int, long long>>, cmp> pq;
for (int i = 0; i < k; ++i){
int u = P[i];
dis[u].first = dis[u].second = 0;
pq.push({u, 0});
}
while(!pq.empty()){
int u = pq.top().first;
long long cur_dis = pq.top().second;
pq.pop();
if (cur_dis != dis[u].second) continue;
for (auto [v, w] : adj[u]){
bool opt = false;
if (cur_dis + w <= dis[v].first){
dis[v].second = dis[v].first;
dis[v].first = cur_dis + w;
opt = true;
}
else if (cur_dis + w < dis[v].second){
dis[v].second = cur_dis + w;
opt = true;
}
if (opt && dis[v].first != inf && dis[v].second != inf)
pq.push({v, dis[v].second});
}
}
return dis[0].second;
}