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↵
↵
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↵
↵
