이번 문제는 다익스트라 알고리즘과 정렬을 통해 해결하였다. 지헌이와 성하의 위치에서 각각 다익스트라 알고리즘을 통해 모든 점으로의 최단 거리를 구하고, 이를 통해 반환받은 최단거리 리스트 두개를 함께 순회하며 지헌이로부터의 거리, 성하로부터의 거리, 장소 번호를 담아 저장하였다. 그리고 이 리스트를 지헌, 성하로부터의 거리의 합, 지헌이로부터의 거리, 장소 번호 순으로 오름차순 정렬을 적용하였고, 이 리스트가 비어있거나, 첫번째 값들을 확인하여 성하의 거리가 지헌이의 거리보다 작을 경우 -1을, 그 외의 경우에는 첫번째 값의 장소 번호를 출력하도록 하였다.

Code

import heapq
v, m = map(int, input().split())
graph = [[] for _ in range(v+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
j, s = map(int, input().split())
def get_dists(cur):
    hq = []
    heapq.heappush(hq, (0, cur))
    dists = [1e9 for _ in range(v+1)]
    dists[cur] = 0
    while hq:
        dist, cur = heapq.heappop(hq)
        if dist > dists[cur]:
            continue
        for nxt, dst in graph[cur]:
            nxt_dst = dist+dst
            if dists[nxt] > nxt_dst:
                dists[nxt] = nxt_dst
                heapq.heappush(hq, (nxt_dst, nxt))
    return dists
def find_place(j_dists, s_dists):
    new_dists = []
    for i in range(1, v+1):
        if i != j and i != s:
            new_dists.append((j_dists[i], s_dists[i], i))
    new_dists.sort(key=lambda x: (x[0]+x[1], x[0], x[2]))
    return new_dists
j_dists = get_dists(j)
s_dists = get_dists(s)
answer = find_place(j_dists, s_dists)
if not answer or answer[0][0] > answer[0][1]:
    print(-1)
else:
    print(answer[0][2])