1238 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

 

다익스트라의 응용이다.

 

N이 1000, M이 10000이므로 다익스트라를 사용해도 충분하다.

 

목적지 X에 갔다가 다시 되돌아와야하므로, 각 노드가 출발점인 경우에서 X까지의 최소거리를 저장하고

X가 목적지 일때 다른 곳 모두의 최소거리의 각각의 합의 최대값을 출력하면 된다.

 

import sys
import heapq
input = sys.stdin.readline
N, M, X = map(int, input().split(" "))
lines = dict()
for i in range(N+1):
  lines[i] = []

for _ in range(M):
  start,end,weight = map(int, input().split(" "))
  lines[start].append( (end, weight) )

# 각각의 모든 노드가 시작점일때의 다익스트라 distance
all_distances = dict()
for i in range(N+1):
  all_distances[i] = None

def dijkstra():
  global N
  global all_distances
  global lines
  global X
  INF = int(1e9)
  

  for start in range(1,N+1):
    distance = [INF] * (N+1)
    distance[start] = 0
    visited = [False] * (N+1)
    q = [] # [(weight, destination)]

    heapq.heappush(q, (0, start))

    while( len(q) > 0 ):
      smallest_dist, smallest_node = heapq.heappop(q)
      visited[smallest_node] = True # 방문처리
      for node in lines[smallest_node]:
        dest, weight = node

        if( visited[dest] == True ): 
          continue
        
        if( (smallest_dist + weight) < distance[dest]):
          distance[dest] = smallest_dist + weight
          heapq.heappush(q, (distance[dest], dest))


    all_distances[start] = list(distance)

  # X 입장에서 모든 경로로 가는 최단거리
  ans = []
  for i in range(1, N+1):
    
    a = all_distances[i][X] # i입장에서 X까지 최단거리
    b = all_distances[X][i] # X입장에서 i까지 최단거리
    ans.append(a+b)

  return max(ans)


print(dijkstra())