結果

問題 No.20 砂漠のオアシス
ユーザー はむ吉🐹
提出日時 2016-03-01 22:24:41
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 601 ms / 5,000 ms
コード長 2,126 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 21,920 KB
最終ジャッジ日時 2024-10-13 05:33:09
合計ジャッジ時間 4,694 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq
import itertools


DELTA = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 2 ** 31 - 1


class Dijkstra(object):

    def __init__(self, h, w, stage, start, goal):
        self.height = h
        self.width = w
        self.start = start
        self.goal = goal
        self.stage = stage
        self.dist = None
        self.init_dist()

    def init_dist(self):
        self.dist = collections.defaultdict(lambda: INF)
        self.dist[self.start] = 0

    def shortest_path_to_goal(self):
        self.init_dist()
        pq = [(self.dist[(r, c)], (r, c))
              for r, c in itertools.product(range(self.height), range(self.width))]
        heapq.heapify(pq)
        while pq:
            (_, (r0, c0)) = heapq.heappop(pq)
            if (r0, c0) == self.goal:
                break
            for dr, dc in DELTA:
                (r, c) = (r0 + dr, c0 + dc)
                if r < 0 or r >= self.height or c < 0 or c >= self.width:
                    continue
                new_length = self.dist[(r0, c0)] + self.stage[r][c]
                if new_length < self.dist[(r, c)]:
                    self.dist[r, c] = new_length
                    heapq.heappush(pq, (new_length, (r, c)))
        return self.dist[self.goal]


def judge(n, v, oasis, stage):
    start = (0, 0)
    goal = (n - 1, n - 1)
    dij = Dijkstra(n, n, stage, start, goal)
    cost_start_to_goal = dij.shortest_path_to_goal()
    if cost_start_to_goal < v:
        return True
    if oasis == (-1, -1):
        return False
    dij.goal = oasis
    cost_start_to_oasis = dij.shortest_path_to_goal()
    dij.start = oasis
    dij.goal = goal
    cost_oasis_to_goal = dij.shortest_path_to_goal()
    return 2 * (v - cost_start_to_oasis) > cost_oasis_to_goal


def main():
    n, v, o_x, o_y = map(int, input().split())
    oasis = (o_y - 1, o_x - 1)
    stage = [array.array("B", map(int, input().split())) for _ in range(n)]
    if judge(n, v, oasis, stage):
        print("YES")
    else:
        print("NO")


if __name__ == '__main__':
    main()
0