[BOJ] 1238. 파티(python)

📌문제

💪아이디어

1. 다익스트라 만들기
   처음에는 마을별 파티마을까지 가는 최소 경로 배열과 파티마을에서 각 마을로 가는 최소 경로 배열을 각각 만들려고했다.
   그러나 시간복잡도가 O(마을 수 * 도로 수)이고 최대 마을 수가 1e3, 최대 도로 수가 1e4일 경우 시간초과라 다른 방법을 찾았다.
   각 마을별 다익스트라를 한번 구해주고 다익스트라 배열을 하나의 배열에 모으면 이차원배열이 나온다. 행은 출발지 열은 도착지로 최소비용 값을 얻을 수 있다.
   

2. 왕복 오래 걸리는 학생 찾기
   최소비용[마을][파티마을] + 최소비용[파티마을][마을]이 각 학생별 왕복 최소 비용이기 때문에 학생별로 탐색하면서 max값을 찾는다.
   

   🥂코드

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

def findRoundTripTime(student):
    distance = [float('inf')] * (n+1)
    heap = []
    distance[student] = 0
    heappush(heap,(0,student))

    while heap:
        cost, cur = heappop(heap)
        if distance[cur] < cost: continue
        for nxt, t in towns[cur]:
            d = t + cost
            if distance[nxt] > d:
                distance[nxt] = d
                heappush(heap,(d,nxt))

    return distance

n, m, x = map(int,input().split())
towns = defaultdict(list)

for _ in range(m):
    a, b, cost = map(int,input().split())
    towns[a].append((b,cost))

dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]

for i in range(1,n+1):
    dist[i] = findRoundTripTime(i)

answer = 0
for i in range(1,n+1):
    answer = max(answer, dist[i][x] + dist[x][i])
print(answer)