본문으로 건너뛰기

1238 - 파티

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

풀이 키워드​

스포주의

다익스트라


풀이 코드​

info
  • 메모리: 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번 뽑았지