Submission #42204570

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
INF = pow(10,20)                        # 無限大とする値。距離や頂点数から考えて十分大きい値にすること
N,M,K = map(int, input().split())         # N:頂点数 M:入力辺数
edge = [set() for _ in range(N+1)]      # edge[i]:頂点iから出ている辺
for _ in range(M):
    A,B = map(int, input().split())     # A:出発元頂点番号 B:行先頂点番号
    edge[A].add(B)                      # (同一頂点に向かう辺は1本であることが問題文で保証されていない場合は、最短辺のみが残るように工夫すること)
    edge[B].add(A)                      # 無向グラフなので逆側にも入れる
stamina = [-1 for _ in range(N+1)]      # ある頂点にいる(ことのできる)警備員の最大HP。各頂点に対し無限大で初期化。
hq = list()                             # 探索用優先度付きキュー。(警備員の残り体力,頂点番号)を追加
heapq.heapify(hq)
for _ in range(K):
    p,h = map(int, input().split())     # A:出発元頂点番号 B:行先頂点番号
    heapq.heappush(hq,(-h,p))           # 最大値を取り出したいので-1倍して入れる
    stamina[p] = h
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import heapq
INF = pow(10,20)                        # 無限大とする値。距離や頂点数から考えて十分大きい値にすること

N,M,K = map(int, input().split())         # N:頂点数 M:入力辺数

edge = [set() for _ in range(N+1)]      # edge[i]:頂点iから出ている辺

for _ in range(M):
    A,B = map(int, input().split())     # A:出発元頂点番号 B:行先頂点番号
    edge[A].add(B)                      # (同一頂点に向かう辺は1本であることが問題文で保証されていない場合は、最短辺のみが残るように工夫すること)
    edge[B].add(A)                      # 無向グラフなので逆側にも入れる

stamina = [-1 for _ in range(N+1)]      # ある頂点にいる(ことのできる)警備員の最大HP。各頂点に対し無限大で初期化。
hq = list()                             # 探索用優先度付きキュー。(警備員の残り体力,頂点番号)を追加
heapq.heapify(hq)

for _ in range(K):
    p,h = map(int, input().split())     # A:出発元頂点番号 B:行先頂点番号
    heapq.heappush(hq,(-h,p))           # 最大値を取り出したいので-1倍して入れる
    stamina[p] = h

while len(hq)!=0:
    h,p = heapq.heappop(hq)             # 優先度付きキューから残り体力最大の点を取り出し
    h = -1 * h                          # 最大値取り出しのために-1倍したのを戻す

    if stamina[p] == h:                 # (Q(v)←altではなく、更新毎に追加しているので、不要パターンがある。最良の場合のみ処理)
        for u in edge[p]:               # 取り出した頂点から出ている全ての辺に対して
            if stamina[u] < h - 1:      
                # より良い残り体力になるなら更新
                stamina[u] = h - 1
                heapq.heappush(hq,(-(h-1),u))   #更新した頂点からの接続点はより良くなる可能性があるので再調査

ans = list()
for i in range(1,N+1):
    if stamina[i] != -1:
        ans.append(i)

print(len(ans))
print(*ans)

Submission Info

Judge Result