파티 ( 1238번 )

1238번: 파티

 

나의 풀이

from collections import deque
import sys

def _back_home(pt_h, n, conn_dict):
    answer = [False] * n
    answer[pt_h - 1] = 0
    queue = deque([(pt_h, 0)])

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

def _go_pt(n, start_point, pt_h, conn_dict):
    answer = [False] * n
    answer[start_point - 1] = 0
    queue = deque([(start_point, 0)])

    while queue:
        now_point, now_cost = queue.popleft()
        for next_point, next_cost in conn_dict[now_point]:
            if (answer[next_point - 1] is False) or (answer[next_point - 1] > now_cost + next_cost):
                answer[next_point - 1] = (now_cost + next_cost)
                queue.append((next_point, now_cost + next_cost))
    return answer[pt_h - 1]

def _main(n, pt_h, conn_dict):
    answer = [0] * n
    go_pt = [0] * n
    for i in range(1, n+1):
        go_pt[i - 1] = _go_pt(n, i, pt_h, conn_dict)
    back_pt = _back_home(pt_h, n, conn_dict)

    for idx in range(n):
        answer[idx] = go_pt[idx] + back_pt[idx]
    return max(answer)

n, m, x = map(int, sys.stdin.readline().rstrip().split())
conn_dict = {i: [] for i in range(1, n + 1)}

for _ in range(m):
    start, end, cost = map(int, sys.stdin.readline().rstrip().split())
    conn_dict[start].append((end, cost))

print(_main(n, x, conn_dict))

 

시간 복잡도

for i in range(1, n+1) : 각 마을 순회 ( 선형 시간 복잡도 )
    _go_pt(n, i, pt_h, conn_dict) : 각 마을 그래프 탐색 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )