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