| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1308483 | StefanSebez | Crocodile's Underground City (IOI11_crocodile) | C11 | 0 ms | 0 KiB |
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,inf=1e9;
const ll INF=1e18;
vector<pair<int,int>>E[N];
int n,m;
ll res[N];
ll mn1[N],mn2[N];
int travel_plan(int n1, int m1, int R[][2], int L[], int K, int P[]){
n=n1,m=m1;
for(int i=0;i<m;i++){
E[R[i][0]].pb({R[i][1],L[i]});
E[R[i][1]].pb({R[i][0],L[i]});
}
for(int i=0;i<n;i++)res[i]=mn1[i]=mn2[i]=INF;
priority_queue<pair<ll,int>>pq;
for(int i=0;i<K;i++){
int u=P[i];
res[u]=0;
pq.push({-res[u],u});
}
while(!pq.empty()){
auto [d,u]=pq.top();pq.pop();
if(-d!=res[u])continue;
for(auto [v,w]:E[u]){
ll x=res[u]+w;
if(x<=mn1[v])mn2[v]=mn1[v],mn1[v]=x;
else if(x<=mn2[v])mn2[v]=x;
if(mn2[v]<res[v]){
res[v]=mn2[v];
pq.push({-res[v],v});
}
}
}
return res[0];
}
