JOI 2018 - Commuter Pass

1. Use Dijkstra's to calculate distances from $s$, $u$, and $v$.
2. Consider a subset of directed edges where each directed edge is part of a shortest path from $s$ to $t$. Note that this subset is a DAG, and can be found by keeping track of the parents of every node when running Dijkstra's.
3. Note that an optimal path will be $u \rightarrow x \rightarrow y \rightarrow v$, where $x \rightarrow y$ is a path on the DAG. Note that any path on the DAG is a valid commuter pass option, and the only node with in-degree 0 is $u$, and the only node with out-degree 0 is $t$ in the DAG.
4. Define dpU(i) = minimum distance from $u$ to any node $x$ such that $x$ is in a path from $s$ to $i$ in the DAG.
5. Define dpV(i) = minimum distance from $v$ to any node $x$ such that $x$ is in a path from $s$ to $i$ in the DAG.
6. The DP transition for dpU(i) is dpU(i) = min(distU[i], dpU(parent_i)) for each parent of i (see dijkstra2 function implementation for more details). dpV's transition is defined similarly.
7. Our answer is dpU(v) + dpV(v). Since edges are bidirectional, an optimal path can also be $v \rightarrow x \rightarrow y \rightarrow u$ where $x \rightarrow y$ is a path on the DAG. We can solve this by rerunning steps 2-7 while switching $u$ and $v$. In Andi's code, steps 2-7 are implemented in the dijkstra2 function.
8. Alternatively, the answer could just be from $u$ directly to $v$ without using the commuter pass.

Implementation

Andi's implementation:

Copy
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<pair<ll, ll>> graph[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;
bool visited[100001];

void dijkstra1(ll start, ll arr[]) {
	fill(visited, visited + 100001, false);

Alternatively, Nathan's implementation. Note that the DP definitions in Nathan's implementation are slightly different than above.