#include #include #include #include #include #include using namespace std; constexpr int inf = 987654321; // N E S W constexpr array dr = {-1, 0, 1, 0}, dc = { 0, 1, 0,-1}; constexpr int dr_size = dr.size(); int N, V, Oc, Or; vector> G, cost; void spfa(vector> &cost, int sr, int sc, int V) { cost.assign(N, vector(N, inf)); // cost[座標] := ダメージ量 cost[sr][sc] = 0; queue> que; que.emplace(sr, sc); vector> inque(N, vector(N, false)); inque[sr][sc] = true; while(!que.empty()) { int r, c; tie(r, c) = que.front(); que.pop(); inque[r][c] = false; for(int i=0; i cost[r][c] + G[nr][nc]) { cost[nr][nc] = cost[r][c] + G[nr][nc]; if(!inque[nr][nc]) { inque[nr][nc] = true; que.emplace(nr, nc); } } } } } int main(void) { scanf("%d%d%d%d", &N, &V, &Oc, &Or); assert(2 <= N && N <= 200); assert(1 <= V && V <= 500); assert((1 <= Or && Or <= N && 1 <= Oc && Oc <= N) || (Or == 0 && Oc == 0)); --Or, --Oc; G.assign(N, vector(N, 0)); for(int r=0; r