Commuter Pass

Explicación

1. Usamos Dijkstra para calcular distancias desde $s$, $u$ y $v$.
2. Consideramos un subconjunto de aristas dirigidas donde cada arista dirigida forma parte de un camino más corto de $s$ a $t$. Notemos que este subconjunto es un DAG, y se puede hallar llevando la cuenta de los padres de cada nodo al ejecutar Dijkstra con $s$ como nodo de partida.
3. Un camino óptimo tendrá la forma $$u \rightarrow x \rightarrow y \rightarrow v$$ o $v \rightarrow x \rightarrow y \rightarrow u$, donde $x \rightarrow y$ es un camino en el DAG. Notemos que cualquier camino en el DAG es una opción válida de pase de viajero.
4. Sin pérdida de generalidad, asumimos que nuestro camino tiene la forma $u \rightarrow x \rightarrow y \rightarrow v$.
5. Definimos $\text{dp}_1(i)$ como la distancia mínima de $u$ a cualquier nodo $x$ tal que $x$ está en un camino de $s$ a $i$ en el DAG.
6. Definimos $\text{dp}_2(i)$ como la distancia mínima de $u$ a $v$ si las aristas del pase de viajero usadas están en un camino de $s$ a $i$ en el DAG.
7. Para cada padre de un nodo $i$, nuestras transiciones son: $$\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. Si el nodo fuente es $s$, entonces la respuesta es $\text{dp}_2(t)$. Para manejar el caso en que el camino óptimo tiene la forma $v \rightarrow x \rightarrow y \rightarrow u$, repetimos el algoritmo para el nodo fuente $t$.
9. Alternativamente, la respuesta podría ser la distancia de $u$ a $v$ sin usar el pase de viajero.

Implementación

Complejidad temporal: $\mathcal{O}(M \log N)$

#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);
 
	priority_queue<pair<ll, ll>> pq;
	pq.push({0, start});
	while (!pq.empty()) {
		ll c, node;
		tie(c, node) = pq.top();
		pq.pop();
 
		if (!visited[node]) {
			arr[node] = -c;
			visited[node] = true;
			for (auto &i : graph[node]) pq.push({c - i.second, i.first});
		}
	}
}
 
void dijkstra2(ll start, ll end) {
	fill(dp[0], dp[0] + 100001, LLONG_MAX / 2);
	fill(dp[1], dp[1] + 100001, LLONG_MAX / 2);
	fill(visited, visited + 100001, false);
 
	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push({0, {start, 0}});
	while (!pq.empty()) {
		ll c, node, par;
		pair<ll, ll> p;
		tie(c, p) = pq.top();
		tie(node, par) = p;
		pq.pop();
 
		if (!visited[node]) {
			visited[node] = true;
			ds[node] = -c;
			dp[0][node] = min(du[node], dp[0][par]);
			dp[1][node] = min(dp[0][node] + dv[node], dp[1][par]);
			for (auto i : graph[node]) pq.push({c - i.second, {i.first, node}});
		} else if (-c == ds[node]) {
			dp[0][node] = min(dp[0][node], dp[0][par]);
			dp[1][node] = min({dp[1][node], dp[0][node] + dv[node], dp[1][par]});
		}
	}
 
	ans = min(ans, dp[1][end]);
}
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	ll n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 0; i < m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}
 
	dijkstra1(u, du);
	dijkstra1(v, dv);
 
	ans = du[v];
 
	dijkstra2(s, t);
	dijkstra2(t, s);
 
	cout << ans << '\n';
	return 0;
}

Alternativamente, la implementación de Nathan . Notemos que las definiciones de DP en la implementación de Nathan son ligeramente distintas a las de arriba.