Hi Codeforces! Commuter Pass ( JOI 2017 — 2018 ) : https://oj.uz/problem/view/JOI18_commuter_pass Now, I will summarize the problem statement:
Given a weighted graph with n vertices and m edges, along with four specific vertices s, t, u, v. We can choose a shortest path from s to t to travel for free. The problem requires us to minimize the travel cost between u and v assuming we optimally select the free path from s to t. We can easily see that the optimal result is the minimum of the direct distance between u and v and the sum of the distance from u to the nearest vertex on the free path from s to t and the distance from v to the nearest vertex on the free path from s to t.
I couldn't solve this problem using a standard Dijkstra algorithm, even though I found the solution (which is also the main approach to solving the problem). However, in the author's sample code, they used a rather unusual variation of Dijkstra. Everything else is implemented as in the standard solution. Can anybody explain me why?
```cpp 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}});
dp[0][0] = dp[1][0] = LLONG_MAX / 2;
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(dv[node], dp[1][par]);
for (auto i : graph[node]) pq.push({c - i.second, {i.first, node}});
} else if (-c == ds[node]) {
if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <=
dp[0][node] + dp[1][node]) {
dp[0][node] = min(du[node], dp[0][par]);
dp[1][node] = min(dv[node], dp[1][par]);
}
}
}
ans = min(ans, dp[0][end] + dp[1][end]);
}
Author 's Code : https://usaco.guide/problems/joi-2018commuter-pass/solution
