[백준][Python] 1504번 특정한 최단경로 - 그래프, BFS

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

1504번: 특정한 최단 경로

 

 

Python

from collections import deque
import sys
input = sys.stdin.readline


n, e = map(int, input().split())
edges = [[] for _ in range(n+1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))
    edges[b].append((a, c))
v1, v2 = map(int, input().split())


def bfs(start, end):
    global edges, n
    if start == end:
        return 0

    d = [-1]*(n+1)
    d[start] = 0
    q = deque([start])
    while q:
        i = q.popleft()
        if i != end:
            for e in edges[i]:
                if d[e[0]] == -1 or d[e[0]] > d[i]+e[1]:
                    d[e[0]] = d[i]+e[1]
                    q.append(e[0])
                    #print(d, i, e)
    if d[end] == -1:  # False로 해두니 총합 0일 때와 False를 구분 못 하기에 -1로
        return -1
    return d[end]


path12 = [bfs(1, v1), bfs(v1, v2), bfs(v2, n)]
path21 = [bfs(1, v2), bfs(v2, v1), bfs(v1, n)]
if -1 in path12 and -1 in path21:
    print(-1)
elif -1 in path12:
    print(sum(path21))
elif -1 in path21:
    print(sum(path12))
else:
    print(min(sum(path12), sum(path21)))