1238 - 파티

정보

• 문제 보기: 1238 - 파티
• 소요 시간: 18분 15초
• 풀이 언어: python
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

다익스트라

풀이 코드

정보

• 메모리: 37636 KB
• 시간: 1656 ms

import sys
from math import inf
import heapq
input = sys.stdin.readline

n, m, x = 0, 0, 0
graph = []

def dijkstra(start, end):
    pq = []
    distance = [inf] * (n+1)
    heapq.heappush(pq, (0, start))
    distance[start] = 0
    
    while pq:
        d, cur = heapq.heappop(pq)
        if distance[cur] < d:
            continue
        
        for v, w in graph[cur]:
            cand = d + w
            if cand < distance[v]:
                heapq.heappush(pq, (cand, v))
                distance[v] = cand

    return distance[end]

def solution():
    global n, m, x, graph
    
    n, m, x = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        v1, v2, w = map(int, input().split())
        graph[v1].append((v2, w)) # 단방향
        
    ans = 0
    for i in range(1, n+1):
        if i == x:
            continue
        ans = max(ans, dijkstra(i,x) + dijkstra(x,i))
    
    print(ans)


if __name__ == '__main__':
    solution()

풀이 해설

graph를 [[] for _ in range(n+1)]로 초기화해야 하는 점이 약간의 유의점

• 원래 None으로 초기화하던 본인의 스타일과 충돌하는 문제 발생
• 예제만 봐도 알듯이 중간에 빠진 숫자의 노드도 있어서 해당 숫자는 다익스트라 함수를 skip해야 함

메모

• 아 왜 3번 뽑았지