[BOJ] 1238. 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

문제: 파티에 다녀오는 최단 거리(왕복)를 구하라.

 

문제 이해하기!!

다익스트라 문제였습니다.

하지만 다익스트라를 한 번만에 푸는 것이 아닌 단 방향 길을 양 방향으로 생각해야 되는 문제에요.

시작하는 지점이 여러 개라고 모두 생각하다가는 시간초과가 날 수 있습니다.

 

제가 푼 방식을 설명하자면,

1. 먼저 도착지점에서 각 마을 파티사람들의 오는 최소거리를 다익스트라로 찾습니다.

2. 단 방향으로 이루어진 길을 반대 방향으로 바꾸어서, 도착지점에서 시작지점으로 사람들의 최소거리를 다익스트라로 찾습니다.

 - 이 부분이 이해 안 될 수도 있는데, 우리가 도착한 지점에서 출발한 지점으로 역 추적한다고 생각하시면 됩니다!

3. 찾은 거리들을 각 마을별로 더합니다.

4. 그 중 최대 값을 출력하면 답이 나옵니다.

끝!

 

코드:

import heapq
from collections import defaultdict
from sys import stdin
#stdin = open('input.txt', 'r')
input = stdin.readline

N, M, X = map(int, input().split())
dic = defaultdict(list)
r_dic = defaultdict(list)
for i in range(M):
    s, e, c = map(int, input().split())
    dic[s].append((c, e))
    r_dic[e].append((c, s))

def djst(dic):
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    Q = [(0, X)]
    visit = [False] * (N + 1)
    while Q:
        c, e = heapq.heappop(Q)
        if visit[e]:
            continue
        dp[e] = c
        visit[e] = True
        for nc, ne in dic[e]:
            heapq.heappush(Q, (nc + c, ne))
    return dp

dp1 = djst(dic)
dp2 = djst(r_dic)

print(max([dp1[i] + dp2[i] for i in range(N+1)]))