🔥

문제

암소 베시는 사과를 두 친구한테 배달해주려고 한다.
베시의 목장은 P(1≤P≤100,000)개의 외양간으로 이루어져있고, C(1≤C≤200,000) 개의 오솔길이 외양간들을 연결하고 있다.
각 외양간에는 편의를 위해서, 1~P까지 번호가 붙여져있다.
목장은 외양간이 정점, 오솔길이 간선인 일반적인 그래프라고 생각하면 된다. 같은 외양간을 연결하는 오솔길은 없고, 오솔길은 양방통행이다.
또 목장은 연결그래프이다. i번째 오솔길은 P1i(1≤P1i≤P)와 P2i(1≤P2i≤P)를 연결하고, 길이는 Di이다. Di들의 합은 2000000000을 넘지 않는다.


베시는 PB(1≤PB≤P)에서 출발한다.
두 친구는 PA1(1≤PA1≤P), PA2(1≤PA2≤P)에 위치해있다.
친구를 방문하는 순서는 중요하지 않고, 두 친구의 목장을 한 번씩 방문하면 된다.
PB, PA1, PA2는 모두 다름이 보장된다.


목장의 정보, 베시와 두 친구들의 위치가 주어졌을 때, 베시가 이동해야 하는 최소 거리를 구하는 프로그램을 작성하여라.

위의 예시에서 베시가 5번 외양간에서 출발하고, 친구가 [1], [4]번 외양간에 있다면 그녀가


5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*


순서로 방문을 하는 것이 최적이다.
이때 이동한 거리는 12이다.

입력

첫 줄에는 C, P, PB, PA1, PA2가 공백을 기준으로 주어진다.
다음 C줄에는 각 오솔길의 정보 P1i,P2i,Di가 공백을 기준으로 주어진다.

출력

베시가 사과를 배달하기 위해서 이동해야 하는 최소 거리를 출력하여라.

예제 1 입력

9 7 5 1 4
5 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3

예제 1 출력

12

Source

from queue import PriorityQueue

pq1 = PriorityQueue()
pq2 = PriorityQueue()
flag = 0

c, p, pb, pa1, pa2 = map(int, input().split())

edge = [[] for _ in range(p + 1)]
dist1 = [0 for _ in range(p + 1)]
dist2 = [0 for _ in range(p + 1)]

for _ in range(c):
	a, b, c = map(int, input().split())
	edge[a].append((b, c))
	edge[b].append((a, c))

pq1.put((1, pb))

# pb -> pa1 or pa2
while(not pq1.empty()):
	tmp = pq1.get()
	d = tmp[0]
	v = tmp[1]

	if(dist1[v] > 0):
		continue
	dist1[v] = d

	for e in edge[v]:
		_d = e[1]
		u = e[0]
		pq1.put((d + _d, u))

if(dist1[pa1] - 1 > dist1[pa2] - 1):
	pq2.put((1, pa2))
	flag = 2
else:
	pq2.put((1, pa1))
	flag = 1

# pa1 -> pa2 or pa2 -> pa1
while(not pq2.empty()):
	tmp = pq2.get()
	d = tmp[0]
	v = tmp[1]

	if(dist2[v] > 0):
		continue
	dist2[v] = d

	for e in edge[v]:
		_d = e[1]
		u = e[0]
		pq2.put((d + _d, u))

if(flag == 1):
	print(dist1[pa1] + dist2[pa2] - 2)
elif(flag == 2):
	print(dist1[pa2] + dist2[pa1] - 2)

참고