| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1289134 | harryleee | Crocodile's Underground City (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<long long, long long>& a, const pair<long long, long long>& b) const {
return a.second > b.second;
}
};
long long travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
vector<vector<pair<long long, long long>>> 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){
long long 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<long long, long long>, vector<pair<long long, 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()){
long long 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]){
if (cur_dis + w < dis[v].first){
dis[v].second = dis[v].first;
if (dis[v].first != dis[v].second)
pq.push({v, dis[v].second});
dis[v].first = cur_dis + w;
}
else if (cur_dis + w < dis[v].second){
dis[v].second = cur_dis + w;
pq.push({v, dis[v].second});
}
}
}
return dis[0].second;