結果

問題 No.20 砂漠のオアシス
ユーザー roarisroaris
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,916 KB
testcase_01 AC 41 ms
53,932 KB
testcase_02 AC 39 ms
53,704 KB
testcase_03 AC 107 ms
77,484 KB
testcase_04 AC 107 ms
77,388 KB
testcase_05 AC 232 ms
85,416 KB
testcase_06 AC 245 ms
86,396 KB
testcase_07 AC 239 ms
86,652 KB
testcase_08 AC 169 ms
86,148 KB
testcase_09 AC 246 ms
86,808 KB
testcase_10 AC 39 ms
54,404 KB
testcase_11 AC 40 ms
53,700 KB
testcase_12 AC 121 ms
77,496 KB
testcase_13 AC 123 ms
77,576 KB
testcase_14 AC 136 ms
78,312 KB
testcase_15 AC 134 ms
78,092 KB
testcase_16 AC 166 ms
80,064 KB
testcase_17 AC 155 ms
78,624 KB
testcase_18 AC 163 ms
79,256 KB
testcase_19 AC 173 ms
79,600 KB
testcase_20 AC 100 ms
76,652 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