[백준] 1238. 파티 - 파이썬

풀이.

다익스트라 알고리즘을 이용해서 출발점에서 도착점까지의 최단 경로 + 도착점에서 출발점까지의 최단 경로를

구해서 최댓값을 출력해주면 된다.

 

소스코드.

 

	# 다익스트라
	import sys
	import heapq
	def dijkstra(start):
	heap = []
	dp = [inf] * (n + 1)
	dp[start] = 0
	heapq.heappush(heap, (0, start))
	while heap:
	now_weight, now = heapq.heappop(heap)
	if dp[now] < now_weight:
	continue
	for next, cost in graph[now]:
	next_weight = now_weight + cost
	if next_weight < dp[next]:
	dp[next] = next_weight
	heapq.heappush(heap, (next_weight, next))
	return dp
	input = sys.stdin.readline
	inf = float('inf')
	n, m, x = map(int, input().split())
	graph = [[] for _ in range(n+1)]
	for _ in range(m):
	u, v, w = map(int, input().split())
	graph[u].append((v,w))
	answer = 0
	for i in range(1, n+1):
	answer = max(answer, dijkstra(i)[x] + dijkstra(x)[i])
	print(answer)

view raw 1238 - 파티.py hosted with ❤ by GitHub