BOJ - 1238

백준 문제 링크
파티

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 먼저 문제의 입력을 n, m, target으로 받고
   graph[시작점].append((끝점, 소요시간)) 해준다.
3. 다익스트라 함수 party를 만들어서
   distance = [INF] * (n + 1)로 지정하고,
   기본 다익스트라 소스 코드를 작성하고 마지막엔 distance를 return
4. 이제 (집 -> target) + (target -> 집)의 값이 최대인 소요시간을 구해야한다. answer = [0] * (n + 1)로 만들어주고

• for i in range(1, n + 1):
  • arr = party[i]
    answer[i] += arr[target] # 집(i) -> target 의 소요시간
    arr2 = party[target]
    answer[i] += arr2[i] # target -> 집(i)의 소요시간
  5. 마지막으로 max(answer)를 출력하면 끝!

👌🏻코드

import heapq

n, m, target = map(int, input().split())

INF = int(1e9)

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

for _ in range(m):
  a, b, c = map(int, input().split())
  
  graph[a].append((b,c))
  
def party(start):
  
  distance = [INF] * (n + 1) 
  
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  
  while q:
      dist , now = heapq.heappop(q)
      
      if distance[now] < dist:
          continue
          
      for i in graph[now]:
          
          cost = dist + i[1]
          
          if cost < distance[i[0]]:
              distance[i[0]] = cost
              heapq.heappush(q, (cost, i[0]))
              
  return distance
             
answer = [0] * (n + 1)
for i in range(1, n + 1):
  arr = party(i)
  answer[i] += arr[target]
  
  arr2 = party(target)
  answer[i] += arr2[i]
  
print(max(answer))