結果

問題 No.20 砂漠のオアシス
ユーザー roarisroaris
提出日時 2019-08-21 17:26:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 268 ms / 5,000 ms
コード長 1,639 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 86,804 KB
最終ジャッジ日時 2024-04-17 16:04:14
合計ジャッジ時間 4,491 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
52,480 KB
testcase_01 AC 49 ms
53,888 KB
testcase_02 AC 48 ms
53,504 KB
testcase_03 AC 123 ms
77,056 KB
testcase_04 AC 126 ms
76,784 KB
testcase_05 AC 250 ms
85,168 KB
testcase_06 AC 268 ms
86,520 KB
testcase_07 AC 264 ms
86,388 KB
testcase_08 AC 185 ms
85,760 KB
testcase_09 AC 265 ms
86,804 KB
testcase_10 AC 47 ms
52,736 KB
testcase_11 AC 48 ms
52,864 KB
testcase_12 AC 142 ms
77,416 KB
testcase_13 AC 142 ms
77,248 KB
testcase_14 AC 160 ms
78,284 KB
testcase_15 AC 156 ms
78,292 KB
testcase_16 AC 190 ms
80,264 KB
testcase_17 AC 179 ms
78,944 KB
testcase_18 AC 185 ms
79,188 KB
testcase_19 AC 193 ms
79,652 KB
testcase_20 AC 118 ms
77,036 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop

def dijkstra(start):
    distance = [10 ** 18] * (N ** 2)
    distance[start] = 0
    priority_queue = []
    heappush(priority_queue, (distance[start], start))
    
    while len(priority_queue) > 0:
        current_dist, current_node = heappop(priority_queue)
        
        if distance[current_node] < current_dist:
            continue
        
        for next_node, w in adj_list[current_node]:
            if distance[next_node] > distance[current_node] + w:
                distance[next_node] = distance[current_node] + w
                heappush(priority_queue, (distance[next_node], next_node))
    
    return distance

N, V, Ox, Oy = map(int, input().split())
Ox -= 1
Oy -= 1
L = [list(map(int, input().split())) for _ in range(N)]
adj_list = [[] for _ in range(N * N)]

for i in range(N):
    for j in range(N):
        if i >= 1:
            adj_list[N*i+j].append((N*(i-1)+j, L[i-1][j]))
        if i <= N - 2:
            adj_list[N*i+j].append((N*(i+1)+j, L[i+1][j]))
        if j >= 1:
            adj_list[N*i+j].append((N*i+j-1, L[i][j-1]))
        if j <= N - 2:
            adj_list[N*i+j].append((N*i+j+1, L[i][j+1]))

distance = dijkstra(0)

if V > distance[N*N-1]:
    print('YES')
else:
    if Ox == -1 and Oy == -1:
        print('NO')
    else:
        dist_to_water = distance[N*Oy+Ox]
        
        if V <= dist_to_water:
            print('NO')
        else:
            V = 2 * (V - dist_to_water)
            distance2 = dijkstra(N*Oy+Ox)
            
            if V > distance2[N*N-1]:
                print('YES')
            else:
                print('NO')
0