BOJ 6118 숨바꼭질

백준 6118 링크

https://www.acmicpc.net/problem/6118

6118번: 숨바꼭질

풀이

그냥 다익스트라

코드

#파이썬pq는 최소힙
import heapq as pq
input = __import__('sys').stdin.readline
n,m = map(int, input().split())
con = [[] for _ in range(n+1)]
dp=[float("inf")]*(n+1)
for _ in range(m):
    a,b = map(int, input().split())
    con[a].append(b);con[b].append(a)
q=[(0,1)]
dp[1]=dp[0]=0
while q:
    cost,n=pq.heappop(q)
    if cost!=dp[n]:continue
    for i in con[n]:
        if dp[i]>cost+1:
            dp[i]=cost+1
            pq.heappush(q,(cost+1, i))
mx=max(dp)
cnt=0
ch=True
for i in range(1,n+1):
    if mx==dp[i]:
        cnt+=1
        if ch:
            print(i,end=' ')
            ch=False
print(mx, cnt)