1167 백준 파이썬

https://0422.tistory.com/104

1967 백준 파이썬

이전 게시글과 거의 똑같은 유형의 문제. 해설은 전 게시글과 동일하기에 쓰지 않겠다.

다만, 차이점은 이전 문제는 BFS로 해결했다면, 이번 문제는 다익스트라로 해결했다.

 

import heapq
INF=int(1e9)
def dik(start):
    heap=[]
    distance=[INF for _ in range(n+1)]
    distance[start]=0
    heapq.heappush(heap,(start,0))
    while heap:
        now,cost=heapq.heappop(heap)
        if distance[now]<cost:
            continue
        for x in g[now]:
            next=x[0]
            tmpcost=x[1]
            if cost+tmpcost<distance[next]:
                distance[next]=cost+tmpcost
                heapq.heappush(heap,(next,distance[next]))
    MAX=0
    where=0
    for x in range(len(distance))[1:]:
        if distance[x]>MAX:
            MAX=distance[x]
            where=x
    return where,MAX
n=int(input())
g=[[]for _ in range(n+1)]
for x in range(n):
    tmp=list(map(int,input().split()))
    for x in range(1,len(tmp),2):
        if tmp[x]!=-1:
            g[tmp[0]].append(tmp[x:x+2])
where,res=dik(1)
where,res=dik(where)
print(res)