1238 파티 [최단경로 알고리즘]

문제를 처음 읽고 음 floyd 알고리즘을 이용해 모든 최단경로를 구하면 되겠군! 했지만 n의 값이 최대 1000이였다.. 1000^3 이면 역시나 될리가 없다

가지치기를 몇번 시도해봤지만 floyd 알고리즘에 대해 수박겉핥기식으로 아는정도라 시도하다가 포기했다.

다시 고민한 결과 모든 정점의 최단경로를 구할필요가 없다는점에서 아이디어를 얻었다.

즉 도착지 정점에서는 각 정점으로 가는 최단경로값은 모두 구해야한다, 하지만 다른 정점에서는 도착지로 가는 정점만 구하면 된다.

즉 이말은 역방향 그래프를 하나더 생성해 정방향 도착지에서 모든정점 한번 역방향 도착지에서 모든 정점 한번 

이런식으로 총 두번 구하면 된다.

소스코드는 bfs로 나와있다. 딱히 다익스트라를 안써도 될것같아 (귀찮아서)  bfs로 구했다

import sys
from collections import deque
read = sys.stdin.readline


def bfs(graph, visit):
    q = deque()
    q.append((x, 0))
    while q:
        now, s = q.popleft()
        for i, w in graph[now]:
            if s + w < visit[i]:
                visit[i] = s + w
                q.append((i, s+w))

n, m, x = map(int, input().split())
visit = [987654321] * (n+1)
r_visit = [987654321] * (n+1)
visit[x] = 0
r_visit[x] = 0

graph = [[] for i in range(n+1)]
r_graph = [[] for i in range(n+1)]
for i in range(m):
    u, v, w = map(int, read().split())
    graph[u].append((v, w))
    r_graph[v].append((u, w))

bfs(graph, visit)
bfs(r_graph, r_visit)

max_num = 0
for i in range(1, n+1):
    max_num = max(max_num, visit[i] + r_visit[i])

print(max_num)