結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー roaris
提出日時 2019-08-21 17:26:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 246 ms / 5,000 ms
コード長 1,639 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 86,808 KB
最終ジャッジ日時 2024-10-09 10:08:53
合計ジャッジ時間 4,203 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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