結果

問題 No.20 砂漠のオアシス
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-03-01 22:24:41
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 590 ms / 5,000 ms
コード長 2,126 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 21,956 KB
最終ジャッジ日時 2024-04-21 06:49:46
合計ジャッジ時間 4,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
11,008 KB
testcase_01 AC 30 ms
11,136 KB
testcase_02 AC 30 ms
11,008 KB
testcase_03 AC 40 ms
11,648 KB
testcase_04 AC 41 ms
11,648 KB
testcase_05 AC 529 ms
21,372 KB
testcase_06 AC 496 ms
21,924 KB
testcase_07 AC 499 ms
21,816 KB
testcase_08 AC 590 ms
21,920 KB
testcase_09 AC 506 ms
21,956 KB
testcase_10 AC 29 ms
11,008 KB
testcase_11 AC 28 ms
11,136 KB
testcase_12 AC 45 ms
11,520 KB
testcase_13 AC 51 ms
11,520 KB
testcase_14 AC 70 ms
11,904 KB
testcase_15 AC 59 ms
11,904 KB
testcase_16 AC 121 ms
13,892 KB
testcase_17 AC 96 ms
12,712 KB
testcase_18 AC 107 ms
13,768 KB
testcase_19 AC 127 ms
13,800 KB
testcase_20 AC 41 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

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