python 백준 17270 연예인은 힘들어

https://www.acmicpc.net/problem/17270

주의점

• 문제 조건을 1,2 번을 만족하는 것으로 갱신 한 후 3번 조건을 처리를 해야함 => 문제 해석에 문제가 발생
• 1,2번 조건에 맞춰 최단 거리의 장소를 구했으면, 그 최단 거리에서 최선의 값을 찾아야함
• 예를들어 a번 장소까지 지헌3 -성하1으로 거리의 합이 4, b번 장소까지 거리의 합이 지헌2-성하3으로 거리의 합이 5 라고 가정
• a장소는 지헌이가 늦으므로 답이 될수 없으므로 b장소가 답이라고 해석할 수 있지만, 최단거리가 4에서 값을 찾아야하는 문제 따라서 답은 -1이 됨

로직

• 다익스트라 알고리즘 이용하여 지헌, 성하 위치에서 최단 거리 계산
• 시작점 제외
• 갈 수 없는 지점 제외
• 각 노드를 만나는 지점으로 하여 반복문을 돌려 최단 거리를 갱신
• 현재 합계 거리가 최단 거리와 같고 지헌이가 늦지 않으면 값 후보에 추가
• 이런 값 후보를 지헌이가 가까운순, 노드 번호 순으로 정렬

from heapq import heappush,heappop
import sys
input = sys.stdin.readline

def dijkstra(N:int,startNode:int)->list[int]:
    global graph
    shortcut = [0]*(N+1)
    ls = [(0,startNode)]
    while ls:
        length,node = heappop(ls)
        for nextNode in graph[node]:
            if nextNode == startNode:
                continue
            nextLength = length+graph[node][nextNode]
            if (shortcut[nextNode] == 0) or nextLength < shortcut[nextNode]:
                shortcut[nextNode] = nextLength
                heappush(ls,(nextLength,nextNode))
    return shortcut

def solution(V:int,J:int,S:int)->int:
    start = {J,S}
    J_length = dijkstra(V,J)
    S_length = dijkstra(V,S)
    ans,value = [-1],10001*V
    for node in range(1,V+1):
        if node in start:
            continue
        if (J_length[node] == 0) or (S_length[node] == 0):
            continue

        nowValue = J_length[node] + S_length[node]
        if (nowValue < value):
            ans = list()
            value = nowValue

        if (nowValue == value) and (J_length[node] <= S_length[node]):
            ans.append(node)
    if ans:
        ans.sort(key= lambda x:(J_length[x],x))
        return ans[0]
    else:
        return -1

V,M = map(int,input().split())
graph = [dict() for _ in range(V+1)]
for _ in range(M):
    a,b,c =map(int,input().split())
    if not graph[a].get(b) or graph[a][b] > c:
        graph[a][b] = c
        graph[b][a] = c

J,S = map(int,input().split())
ans = solution(V,J,S)
print(ans)