#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 dijk(vector> &cost, int sr, int sc, int V) { cost.assign(N, vector(N, inf)); // cost[座標] := ダメージ量 cost[sr][sc] = 0; priority_queue, vector>, greater>> pq; pq.emplace(0, sr, sc); while(!pq.empty()) { int dm, r, c; tie(dm, r, c) = pq.top(); pq.pop(); if(dm == V) { continue; } for(int i=0; i cost[r][c] + G[nr][nc]) { cost[nr][nc] = cost[r][c] + G[nr][nc]; pq.emplace(cost[nr][nc], 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