Contest Duration: - (local time) (100 minutes) Back to Home
Official

## E - 潜入 / Sneaking Editorial by en_translator

Among the four given moves, if we didn’t have the last move, we can solve the problem in a total of $$O(RC \log (RC))$$ time with Dijkstra’s algorithm. How can we handle the last move?
If the cost of the move was $$i$$ instead of $$1+i$$, we can add an edge of cost $$1$$ from $$(r, c)$$ to $$(r-1,c)$$ so that we can take into account the move of cost $$i$$.
As for cost $$1+i$$, the following procedures of adding edges are effective:

• Double each vertex. Now we assume we have two kinds of vertices, normal $$(r, c)$$ and intermediate $$(r, c)$$.
• Add an edge of cost $$1$$ from normal $$(r, c)$$ to intermediate $$(r, c)$$
• Add an edge of cost $$1$$ from intermediate $$(r, c)$$ to intermediate $$(r-1, c)$$
• Add an edge of cost $$0$$ from intermediate $$(r, c)$$ to normal $$(r, c)$$

Now we can see that the moves can be represented as a graph with $$O(RC)$$ number of vertices and $$O(RC)$$ number of edges, thus we can solve the problem in a total of $$O(RC \log (RC))$$ with Dijkstra’s algorithm.

Sample Code (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
bool chmin(int& a, int b){ if(a > b){ a = b; return 1; } return 0; }

int main(){
int R, C;
cin >> R >> C;
vector A(R, vector<int>(C - 1)), B(R - 1, vector<int>(C));
for(auto& a : A) for(int& i : a) cin >> i;
for(auto& b : B) for(int& i : b) cin >> i;
vector cost(2, vector(R, vector(C, 0x3fffffff)));
priority_queue q(greater<>{}, vector<tuple<int, int, int, int>>{});
auto update = [&](int f, int r, int c, int x){
if(chmin(cost[f][r][c], x)) q.emplace(x, f, r, c);
};
update(0, 0, 0, 0);
while(q.size()){
auto [x, f, r, c] = q.top();
q.pop();
if(cost[f][r][c] != x) continue;
if(f){
update(0, r, c, x);
if(r) update(1, r - 1, c, x + 1);
}
else{
update(1, r, c, x + 1);
if(r + 1 < R) update(0, r + 1, c, x + B[r][c]);
if(c) update(0, r, c - 1, x + A[r][c - 1]);
if(c + 1 < C) update(0, r, c + 1, x + A[r][c]);
}
}
cout << cost[0].back().back() << endl;
}


Sample Code (Python)

from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

R, C = map(int, input().split())
data = []
row = []
column = []
for i in range(R):
a = list(map(int, input().split()))
for j in range(C - 1):
x = i * C + j
y = i * C + j + 1
row += [x, y]
column += [y, x]
data += [a[j], a[j]]
for i in range(R - 1):
a = list(map(int, input().split()))
for j in range(C):
x = i * C + j
y = i * C + j + C
row += [x, y + R * C]
column += [y, x + R * C]
data += [a[j], 1]
for i in range(R):
for j in range(C):
x = i * C + j
y = x + R * C
row += [x, y]
column += [y, x]
data += [1, 0]
g = csr_matrix((data, (row, column)))
print(int(shortest_path(g, indices=0)[R * C - 1]))


posted:
last update: