BOJ 1167 PS일기

요구사항

10만개 이하 정점에 양방향 간선이 여러개 주어졌을 때, 가장긴 정점간의 거리를 구해야한다.

문제접근

임의의 정점을 하나고른뒤 가장 먼 지점을 찾고 다시 그 지점에서 가장 먼 지점간의 거리를 찾도록 하였다.

데이터 흐름

입력으로 주어지는 정점간의 비용들을 음수로 저장하고, 본인이 임의로 지정한 1번 정점을 고르고 다익스트라를 통해 정점 B를 구한다. 그리고 다시한번 B정점에서 다익스트라를 통해 정점 C를 구한다. B정점에서 C정점간의 비용을 음수로 출력한다.

import heapq

v,*m = open(0)
v = int(v)
info = dict()
for i in m:
    data = [*map(int, i.split(' '))]
    info[data[0]] = []
    j = 1
    while data[j] != -1:
        info[data[0]].append( (data[j], -data[j + 1]) )
        j += 2

def djk(start):
    hq = [(0,start)]
    inf = 2**99
    d = [inf for _ in range(100001)]
    d[start] = 0
    answer = start
    answerCost = inf
    visited = set()
    while hq:
        cost, curr = heapq.heappop(hq)
        if curr in visited:
            continue
        visited.add(curr)
        if d[curr] != cost:
            continue
        if cost < answerCost:
            answerCost = cost
            answer = curr
        for nxt,cost in info[curr]:
            if d[nxt] <= d[curr] + cost:
                continue
            d[nxt] = d[curr] + cost
            heapq.heappush(hq, (d[nxt], nxt) )
    return (answer,answerCost)

print(-djk(djk(1)[0])[1])