[백준]1238 파티

1. 풀이

1) 다음의 두가지 거리가 필요하다.

(파티장 x에서 a까지의 최단거리) + (a에서 파티장x까지 최단거리)

2) (파티장 x에서 a까지의 최단거리) : X를 시작점으로 다익스트라를 이용해서 구한다

3) (a에서 파티장x까지 최단거리) : edge를 모두 반대방향으로 바꾼 후(cost는 그대로) 다익스트라.

위가 성립하는 이유는

(graph에서 a->b 까지의 최단거리) == (edge의 방향을 바꾼 graph에서 b->a까지의 최단거리) 이기 때문에 자명하다.

 

2. 소스코드

import heapq

#input
N,M,X=map(int,input().split())
graph={}
graphR={}
for i in range(1,N+1):
    graph[i]=[]
    graphR[i]=[]
for i in range(M):
    a,b,cost=map(int,input().split())
    graph[a].append([b,cost])
    graphR[b].append([a,cost])
maxNum=10000000
nodeDist=[maxNum for node in range(N+1)]
nodeDistR=[maxNum for node in range(N+1)]

def dijkstra(nodeDist,graph):
    dij=[[0,X]]
    nodeDist[X]=0
    heapq.heapify(dij)
    while(dij):
        temp=heapq.heappop(dij)
        nowCost=temp[0]
        nowNode=temp[1]
        # 이미방문되었으면 통과해(첫방문이 최솟값임이 보장됨)
        if nodeDist[nowNode]!=nowCost:
            continue
        for toNode,toCost in graph[nowNode]:
            if nowCost+toCost<nodeDist[toNode]:
                nodeDist[toNode]=nowCost+toCost
                heapq.heappush(dij,[nodeDist[toNode],toNode])

#역방향(각 마을에서 X까지의 최단거리)
dijkstra(nodeDistR,graphR)
#순방향(X에서 각마을까지 최단거리)
dijkstra(nodeDist,graph)
#합
dist=[nodeDistR[i]+nodeDist[i] for i in range(1,N+1)]
print(max(dist))