| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1013434 | 2024-07-03T14:31:28 Z | Error404 | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pi>
#define pb push_back
#define INF 1000000000000
#define endl '\n'
#define int ll
#define pii pair<pi,ll>
const int MAX = 1e5+1;
vpi g[MAX];
ll dis[MAX][2];
ll travel_plan(int n,int m, int R[m][2], int L[m],int k, int P[n]){
ll a,b,c,from;
for(int i = 0; i < m; i++){
a = R[i][0];
b = R[i][1];
c = L[i];
g[a].pb({b,c});
g[b].pb({a,c});
}
priority_queue<pii, vector<pii>, greater<pii>>pq;
for(int i = 0; i < n; i++){
dis[i][0]=INF;
dis[i][1]=INF;
}
for(int i =0 ; i < k; i++){
dis[P[i]][0]=0;
dis[P[i]][1]=0;
pq.push({{0,0},P[i]});
}
while(!pq.empty()){
a = pq.top().f.f;
b = pq.top().f.s;
from = pq.top().s;
for(pi i : g[from]){
int to = i.f;
int w= i.s;
if(dis[to][0]>= b+w){
dis[to][1] = dis[to][0];
dis[to][0] = b+w;
pq.push({{dis[to][0],dis[to][1]}, to});
}
else if(dis[to][1]>=b+w){
dis[to][1] = b+w;
pq.push({{dis[to][0],dis[to][1]}, to});
}
}
pq.pop();
}
if(dis[0][1]==INF) return -1;
else return dis[0][1];
}