[백준] 1238 파티, python

https://www.acmicpc.net/problem/1238

1238번: 파티

from sys import stdin;input = stdin.readline
from heapq import heappop, heappush
def dijkstra(start):
    q = [(0, start)]
    while q:
        cur_w, cur = heappop(q)
        if distance_matrix[i][cur] > cur_w:
            distance_matrix[i][cur] = cur_w
            for adj, adj_w in linked_list[cur]:
                if adj_w + cur_w < distance_matrix[i][adj]:
                    heappush(q, (adj_w + cur_w, adj))


N, M, X = map(int, input().split())
linked_list = [list() for _ in range(N + 1)]
for _ in range(M):
    s, *ew = map(int, input().split())
    linked_list[s].append(ew)

INF = 2100000000
distance_matrix = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    dijkstra(i)

answer = 0
for i in range(1, N + 1):
    tmp = distance_matrix[i][X] + distance_matrix[X][i]
    if answer < tmp:
        answer = tmp
print(answer)

모든 구간을 한번씩 순회하며 최소거리를 구하는 알고리즘이다.

 

from sys import stdin;input = stdin.readline
from heapq import heappop, heappush
def dijkstra(start, linked_list, distance):
    heap = [(0, start)]
    distance[start] = 0
    while heap:
        cur_w, cur = heappop(heap)
        if distance[cur] < cur_w: continue
        for adj, adj_w in linked_list[cur]:
            if distance[adj] > adj_w + cur_w:
                distance[adj] = adj_w + cur_w
                heappush(heap, (distance[adj], adj))

N, M, X = map(int, input().split())
linked_list1 = [list() for _ in range(N + 1)]
linked_list2 = [list() for _ in range(N + 1)]
for _ in range(M):
    s, e, w = map(int, input().split())
    linked_list1[s].append((e, w))
    linked_list2[e].append((s, w))

INF = 2100000000
dist1 = [INF for _ in range(N + 1)]
dist2 = [INF for _ in range(N + 1)]
dijkstra(X, linked_list1, dist1)
dijkstra(X, linked_list2, dist2)

answer = 0
for i in range(1, N + 1):
    tmp = dist1[i] + dist2[i]
    if answer < tmp:
        answer = tmp
print(answer)

X부터 각 지점까지의 거리를 각각 구하는 알고리즘이다. 모두 단방향이므로 반대방향으로 갈수있게 만들었고(dist2) 두번의 다익스트라를 사용하여 각 지점마다 최소 거리를 구하였다.