Baltic OI 2017 - Toll

Solution

Split the graph into $N/K$ "layers" with $K$ nodes each. Notice how this graph somewhat resembles a neural network.

Let $dp[a][b][x][y]$ denote the minimum cost of a path between nodes $Ka+x$ to $Kb+y$.

For any triple $a<b<c$, the following recurrence holds:

(Similar to the Floyd-Warshall recurrence).

To finish, we can use any algorithm that allows us to quickly answer static range queries (ex. divide & conquer). Here we'll use a sparse table. Instead of storing each DP state, we can store only $dp[i][i+2^j][x][y]$ for each $i$, $j$, $x$, and $y$. Then we can find the value of $dp[\lfloor A/K\rfloor ][\lfloor B/K\rfloor ][A\%K][B\%K]$ in $\mathcal{O}(K^3\log N)$ time per query with binary jumping. This gives a time complexity of $\mathcal{O}(K^3(N+O)\log N)$.

Code

1#include <bits/stdc++.h>
2using namespace std;
3
4int k, n, m, o;
5int dp[50000][17][5][5], ans[5][5], tmp[5][5];
6
7void combine(int target[5][5], int a[5][5], int b[5][5]) {
8    for (int x = 0; x < k; x++) {
9        for (int y = 0; y < k; y++) {
10            for (int z = 0; z < k; z++) {