# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1187877 | yoruonivamp | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, vector<vector<int>> R, vector<int> L, int K, vector<int> P){
set<int> out;
for(auto u: P) out.insert(u);
vector<vector<pair<int,int>>> adj(N+1);
for(int i = 0; i < M; i++){
adj[R[i][0]].emplace_back(R[i][1],L[i]);
adj[R[i][1]].emplace_back(R[i][0],L[i]);
}
vector<bool> vis(N+1,false);
vector<int> dis(N+1,0x3f3f3f3f);
dis[0] = 0;
int cntway = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.emplace(0,0);
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(out.find(u)!=out.end()){
cntway++;
if(cntway==K) return d;
}
if(vis[u]) continue;
vis[u] = true;
for(auto [v,dd]: adj[u]){
if(dis[v]>dis[u]+dd){
dis[v]=dis[u]+dd;
pq.emplace(dis[v],v);
}
}
}
}