Explanation

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 with $s$ as the starting node.
3. An optimal path will either be in the form $u \rightarrow x \rightarrow y \rightarrow v$ or $v \rightarrow x \rightarrow y \rightarrow u$, where $x \rightarrow y$ is a path on the DAG. Note that any path on the DAG is a valid commuter pass option.
4. Without loss of generality, assume that our path has the form $u \rightarrow x \rightarrow y \rightarrow v$.
5. Define $\text{dp}_1(i)$ as the minimum distance from $u$ to any node $x$ such that $x$ is on a path from $s$ to $i$ in the DAG.
6. Define $\text{dp}_2(i)$ as the minimum distance from $u$ to $v$ if the commuter pass edges used are on a path from $s$ to $i$ in the DAG.
7. For each parent of a node $i$, our transitions are:

   $$\begin{aligned} \text{dp}_1(i) &= \min\!\left\{ \text{dp}_1(i),\; \text{dist}_u(i),\; \text{dp}_1(\text{par}_i) \right\}, \\ \text{dp}_2(i) &= \min\!\left\{ \text{dp}_2(i),\; \text{dp}_1(i) + \text{dist}_v(i),\; \text{dp}_2(\text{par}_i) \right\}. \end{aligned}$$
8. If the source node is $s$, then the answer is $\text{dp}_2(t)$. To handle the case where the optimal path has the form $v \rightarrow x \rightarrow y \rightarrow u$, we repeat the algorithm for the source node $t$.
9. Alternatively, the answer could be the distance from $u$ to $v$ without using the commuter pass.

Implementation

Time Complexity: $\mathcal{O}(M \log N)$

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.