[boj/python] 1238번 파티

import sys
import heapq
input = sys.stdin.readline
INF= (int)(1e8)
N,M,X=map(int,input().split())
lst=[[] for _ in range(N+1)]


for i in range(M):
    start,end,cost = map(int,input().split())
    lst[start].append((end,cost))

# 집 -> x까지 다익스트라 x-> 집까지 다익스트라 2회 수행

def dijkstra(start,):

    q = []
    distance = [INF]*(N+1)
    distance[start] = 0
    heapq.heappush(q,(start,0))

    while q:
        node,dist=heapq.heappop(q)
        if distance[node]<dist:
            continue
        else:
            for next in lst[node]:
                cost = next[1]+distance[node]
                if(cost<distance[next[0]]):
                    distance[next[0]]=cost
                    heapq.heappush(q,(next[0],cost))
    return distance


# x에서 시작하는거 (x에서 시작하는거 미리 짱박아두고 시작)
ans = dijkstra(X)
ans[0]=0
print(ans)
# i에서 x까지
for i in range(1,N+1):
    if i==X:
        continue
    else:
        res = dijkstra(i)
        # x가 종착지인거 고르기
        ans[i] += res[X]


print(max(ans))

 

✅ 문제를 풀면서 잘 못 생각했던거

 

n개의 정점에서 X까지 최단거리 + X라는 정점에서 n까지 최단거리이면 

X라는 정점에서 n까지 최단거리 -> 다익스트라 1회 수행

n개의 정점에서 X까지 최단거리 -> 다익스트라 n회 수행을 해주면 됐다

그니까 애초에 X에서 시작은 1번만 하면 되니까 짱박아두고 시작하면 된다. (이걸 못해서 n번 돌리고 있었네 n이 1000까지 가는데)