[백준/python] 1238 파티

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

1238번: 파티

문제 해결 

1. n번의 마을에 사는 학생 1명이 x번 마을로 가는 최단 경로 값을 구해야한다. 즉, 1-2-3-4-...-n번 마을에 해당하는 학생이 x 마을에 가는 최단경로의 모든 값을 구해야한다.

2. n번 마을에서 x번 마을로 갔다가 돌아오는 왕복값을 계산해주어야 한다. 이때 도로가 단방향이므로 갈 때의 최단 경로와 돌아올 때의 최단 경로는 다르기 때문에 각각에 대해 구해야한다.

이를 구현하기 위해서 

1. 각각의 학생마다 다익스트라 함수를 실행하여 최단경로 값을 구해준다. 이를 위해 조심해야 할 점이 있다. 원래 node의 초기값은 다익스트라 함수 외부에서 선언을 해주었지만 다익스트라 함수 내부에서 선언하여 n번의 학생 마다 선언해주어야 한다.

2. 다익스트라 함수를 각각의 학생마다 실행하기 위해서 for문으로 시작점을 날린다. 

---

전체 코드

import sys; input=sys.stdin.readline
import heapq

def dijkstra(start, end):
    q = []
    # 각자의 집에서 하나하나 구하는 것이므로 node를 함수가 실행될 때 마다 초기화
    node = [INF] * (n+1)
    heapq.heappush(q, (0, start))
    node[start] = 0
    
    while q:
        d, now = heapq.heappop(q)
        if node[now] < d: continue
        
        for i in graph[now]:
            dst = i[0]
            cost = d+i[1]
            
            if cost < node[dst]:
                heapq.heappush(q, (cost, dst))
                node[dst] = cost

    return node[end]

# main 
n,m,x = map(int, input().split())

graph = [[] for _ in range(n+1)]
INF = int(1e9)

for _ in range(m):
    i, j, w = map(int, input().split())
    graph[i].append((j, w))
    
t = 0
# 각자의 집에서 x 마을까지의 최단 경로 + x 마을에서 각자의 집까지의 최단 경로 
for i in range(1, n+1):
    if i == x : continue
    # 중에서 최댓값
    t = max(t, dijkstra(i,x)+dijkstra(x,i))

print(t)