특정한 최단 경로 ( 1504번 )

1504번: 특정한 최단 경로

 

나의 풀이

from collections import deque
import sys

def _main_conn_dict(n, line_ct):
    conn_dict = {i: [] for i in range(1, n+1)}
    for _ in range(line_ct):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        conn_dict[a].append((b, c))
        conn_dict[b].append((a, c))
    return conn_dict

def _case_cr(routing, n, conn_dict):
    answer = 0
    for start, end in routing:
        now_visit = _bfs(start, n, conn_dict)
        if (now_visit[end - 1] == float('inf')):
            return float('inf')
        answer += now_visit[end - 1]
    return answer

def _bfs(start, n, conn_dict):
    visit = [float('inf')] * n
    visit[start - 1] = 0
    queue = deque([(start, 0)])

    while queue:
        now_point, now_cost = queue.popleft()
        for next_point, next_cost in conn_dict[now_point]:
            moving_cost = (now_cost + next_cost)
            if (visit[next_point - 1] > moving_cost):
                visit[next_point - 1] = moving_cost
                queue.append((next_point, moving_cost))
    return visit

n, e = map(int, sys.stdin.readline().rstrip().split())
conn_dict = _main_conn_dict(n, e)
v1, v2 = map(int, sys.stdin.readline().rstrip().split())

## case1 (1 >> v1 >> v2 >> n)
## case2 (1 >> v2 >> v1 >> n)
case1 = _case_cr([(1, v1), (v1, v2), (v2, n)], n, conn_dict)
case2 = _case_cr([(1, v2), (v2, v1), (v1, n)], n, conn_dict)

if (case1 == float('inf')) and (case2 == float('inf')):
    print(-1)
else:
    print(min(case1, case2))

 

시간 복잡도

def _bfs(start, n, conn_dict) : 그래프 탐색 함수로 모든 노드와 해당 노드의 간선 탐색 ( O(n + e) )
해당 파이썬 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )