[백준] 1238 - 파티

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

1238번: 파티

문제 한줄 이해

- N개의 숫자로 구분된 마을에 각각 한 명의 학생이 있을 때 X번 마을에서 학생들이 파티를 하기로 했다. 이때 마을에서 마을로 연결하는 단방향 거리가 있을 때 가장 많은 거리를 이동해야하는 학생의 거리값 구하기.

생각난 풀이

1번째 방법: 문제를 읽고 생각난 필요한 조건들

1. 각 마을들을 가중치에 따라 연결하고 있다. -> 다익스트라 알고리즘이나 최소스패닝 문제일거란 예상 -> 단방향이라는 키워드에 다익스트라 확신

2. 문제에서는 단순히 x마을로 가는 값뿐만 아니라 갔다가 돌아와야하는 조건도 걸었다. -> 그렇다면 i번째 마을에서 x번째로 가는 값과 x번째에서 i번째로 가는 값 더하기

import sys
import heapq
n,m,x = map(int,sys.stdin.readline().split())
city = [[]for i in range(n+1)]

for i in range(m):
    a,b,v = map(int,sys.stdin.readline().split())
    city[a].append((b,v))  #단방향

def dik(start,end):
    hq = []
    dis = [1e9] * (n+1)
    heapq.heappush(hq,(0,start))
    dis[start] = 0
    while hq:
        nowd, nowx = heapq.heappop(hq)
        
        if dis[nowx] < nowd:
            continue
        
        for i in city[nowx]:
            newd = nowd + i[1]
            if newd < dis[i[0]]:
                dis[i[0]] = newd
                heapq.heappush(hq,(newd,i[0]))
    return dis[end]

result = 0
for i in range(1,n+1):
    sub = dik(i,x) + dik(x,i)
    if result < sub:
        result = sub
print(result)