import std; // 構造体のままダイクストラ(ただし、重みはメンバ変数として管理)を試してみる struct node { int y; int x; int weight; } void main () { // input int H, W; readln.read(H, W); int[][] A = new int[][](H-2, 0); foreach (i; 0..H-2) { A[i] = 0 ~ readln.split.to!(int[]); } // グラフ構築 int[] dxy = [-1, 0, 1]; node[][][] graph = new node[][][](H-2, W+1, 0); foreach (i; 0..H-2) { foreach (j; 0..W+1) { // 8方向に辺を張る foreach (dy; dxy) { foreach (dx; dxy) { if (dy == 0 && dx == 0) { continue; } if (H-2 <= i+dy || W+1 <= j+dx || i+dy < 0 || j+dx < 0) { continue; } if (A[i+dy][j+dx] == -1) { continue; } graph[i][j] ~= node(i+dy, j+dx, A[i+dy][j+dx]); } } } } solve(H, W, A, graph); } struct toNode { int y; int x; int totalCost; } void solve (int H, int W, int[][] A, node[][][] graph) { int[][] comfirmedCost = new int[][](H-2, W+1); foreach (ref c; comfirmedCost) { c[] = int.max; } BinaryHeap!(Array!toNode, "a.totalCost > b.totalCost") PQ; // 最初の一列はタダで張れるので、最初の一列のどこかを確定頂点にする PQ.insert(toNode(0, 0, 0)); while (!PQ.empty) { auto shortest = PQ.front; PQ.removeFront; if (comfirmedCost[shortest.y][shortest.x] < shortest.totalCost) { continue; } comfirmedCost[shortest.y][shortest.x] = shortest.totalCost; // 新しく追加された確定頂点から候補を伸ばす foreach (to; graph[shortest.y][shortest.x]) { if (to.weight + shortest.totalCost < comfirmedCost[to.y][to.x]) { PQ.insert(toNode(to.y, to.x, to.weight + shortest.totalCost)); comfirmedCost[to.y][to.x] = to.weight + shortest.totalCost; } } } // 端に到達できたかチェック int ans = int.max; foreach (i; 0..H-2) { ans = min(ans, comfirmedCost[i][W]); } if (ans == int.max) { writeln(-1); } else { writeln(ans); } } void read(T...)(string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }