| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1200548 | PlayVoltz | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include "crocodile.h"
#include <bits/stdc++h.>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int travel_plan(int n, int m, int R[][2], int L[], int k, int vect[]){
vector<vector<pii> > graph(n);
for (int i=0; i<m; ++i){
graph[R[i][0]].pb(mp(R[i][1], L[i]));
graph[R[i][1]].pb(mp(R[i][0], L[i]));
}
vector<vector<int> > dj(n, vector<int>(2, INT_MAX/2));
priority_queue<pii, vector<pii>, greater<pii> > pq;
for (int i=0; i<k; ++i){
dj[vect[i]][0]=dj[vect[i]][1]=0;
pq.push(mp(0, vect[i]));
}
while (pq.size()){
int d=pq.top().fi, node=pq.top().se;
pq.pop();
if (d>dj[node][1])continue;
for (auto num:graph[node]){
if (num.se+d<dj[num.fi][0]){
pq.push(mp(dj[num.fi][0], num.fi));
dj[num.fi][1]=dj[num.fi][0];
dj[num.fi][0]=num.se+d;
}
else if (num.se+d<dj[num.fi][1]){
dj[num.fi][1]=num.se+d;
pq.push(mp(dj[num.fi][1], num.fi));
}
}
}
return dj[0][1];
}