Crocodile
A network of N chambers connected by M bidirectional corridors with travel times. Some K chambers are exits. A person starts at chamber 0. After choosing which corridor to take, a crocodile may block it, forcing the p...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
A network of $N$ chambers connected by $M$ bidirectional corridors with travel times. Some $K$ chambers are exits. A person starts at chamber $0$. After choosing which corridor to take, a crocodile may block it, forcing the person to take the second-best option. Find the minimum guaranteed escape time from chamber $0$ under optimal adversarial play by the crocodile.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Insight
Since the crocodile always blocks the best option, the guaranteed escape cost from any node equals the second-shortest distance to an exit. We track the two shortest distances to any exit for each node.
Algorithm: Modified Multi-Source Dijkstra
Initialize all exits with $d_1 = d_2 = 0$.
Use a min-heap keyed on $d_2$. A node is ``finalized'' when its $d_2$ is determined.
When finalizing node $u$ (with second-best distance $d_2[u]$), for each neighbor $v$ via edge of weight $w$: the candidate distance is $d_2[u] + w$. Update $d_1[v]$ and $d_2[v]$ accordingly:
If $d_2[u] + w < d_1[v]$: shift $d_1[v]$ to $d_2[v]$ and set $d_1[v] = d_2[u] + w$.
Else if $d_2[u] + w < d_2[v]$: set $d_2[v] = d_2[u] + w$.
When $d_2[v]$ improves, push $(d_2[v], v)$ into the heap. enumerate
The answer is $d_2[0]$.
Correctness
Theorem.
Using $d_2[u]$ (the second-best distance) for relaxation correctly computes the guaranteed escape cost.
Proof.
From node $u$, the person's optimal strategy is to always head toward the best available corridor leading to an exit. The crocodile blocks the best choice, forcing the person to use the second-best option. Hence the guaranteed cost from $u$ is $d_2[u]$.
When relaxing from $u$ to $v$, arriving at $u$ costs at least $d_2[u]$ (guaranteed), plus $w$ to traverse the edge. This candidate replaces $d_1[v]$ or $d_2[v]$ if it improves either. Dijkstra's monotonicity ensures that when $d_2[u]$ is finalized, no shorter path to $u$ via two distinct routes exists.
Complexity
Time: $O((N + M) \log N)$.
Space: $O(N + M)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<vector<pair<int,int>>> adj(N);
for(int i = 0; i < M; i++){
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
const long long INF = 1e18;
// d[v][0] = best distance, d[v][1] = second best distance
vector<array<long long, 2>> d(N, {INF, INF});
// Min-heap: (distance, node) -- we push when d2 is set
priority_queue<pair<long long,int>, vector<pair<long long,int>>,
greater<pair<long long,int>>> pq;
for(int i = 0; i < K; i++){
d[P[i]][0] = d[P[i]][1] = 0;
pq.push({0, P[i]});
}
vector<bool> done(N, false);
while(!pq.empty()){
auto [dist, u] = pq.top(); pq.pop();
if(done[u]) continue;
if(dist > d[u][1]) continue;
done[u] = true;
for(auto [v, w] : adj[u]){
long long nd = d[u][1] + w; // use second-best from u
if(nd < d[v][0]){
d[v][1] = d[v][0];
d[v][0] = nd;
} else if(nd < d[v][1]){
d[v][1] = nd;
} else {
continue;
}
if(d[v][1] < INF){
pq.push({d[v][1], v});
}
}
}
return (int)d[0][1];
}
// Standalone main for testing
int main(){
int N, M, K;
cin >> N >> M >> K;
// Read edges
int (*R)[2] = new int[M][2];
int *L = new int[M];
for(int i = 0; i < M; i++){
cin >> R[i][0] >> R[i][1] >> L[i];
}
int *P = new int[K];
for(int i = 0; i < K; i++) cin >> P[i];
cout << travel_plan(N, M, R, L, K, P) << "\n";
delete[] R;
delete[] L;
delete[] P;
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.