오늘의 알고리즘 boj-1238

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

풀이

정점의 갯수가 1000개에 간선의 갯수는 10000개라면 다익스트라로 최단거리를 구해 정답을 얻을 수 있을 것 같다.

start지점으로부터의 거리 distances 테이블을 INF값으로 초기화 해주고 거리 0 start를 우선순위 큐에 넣어 순회를 시작한다.

순회시에 거리가 가장 가까운 노드들을 택해 그 노드들에서 연결된 곳들의 거리를 갱신해준다

중요한건 거리테이블이 이미 현재 가중치 + 현재로부터 이동할 가중치 값보다 작거나 같으면 업데이트 해줄 필요가 없으니 continue로 넘어간다.

마지막으로 거리 테이블을 업데이트 해주고 우선순위큐에 다음 노드를 넣어준다.

마지막으로 반환값은 문제에서 요구하는 값은 오고 가는 길이니까 start와 to 값을 함수 매개변수로 받아서 distances[to]로 설정해주면 거리값을 반환해서 더해주면 오고 가는길을 쉽게 구할 수 있을 것 같다.

이제 마지막으로 정점 순회를 통해 home값을 구해주고 home에서 party_place, party_place에서 home까지 양쪽 값을 구해 total_distances에 값을 더해주고 최종적으로 max값을 프린트해주면 파티장소와 집을 오가는 최대거리를 구할 수 있다.

import heapq
import sys
input = sys.stdin.readline


def get_shortest_way_from_start(start, to):
    INF = int(10e9)
    distances = [INF] * (N+1)
    distances[start] = 0

    distance_check_queue = []
    heapq.heappush(distance_check_queue, (0, start))

    while distance_check_queue:
        cur_weight, cur_node = heapq.heappop(distance_check_queue)
        
        if distances[cur_node] != cur_weight: continue
        
        for next_weight, next_node in graph[cur_node]:
            cur_distance = distances[cur_node] + next_weight
            if distances[next_node] <= cur_distance: continue
            distances[next_node] = cur_distance
            heapq.heappush(distance_check_queue,(distances[next_node], next_node))
            
    return distances[to]



if __name__ == '__main__':

    N, M, party_place = map(int, input().split())

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

    for _ in range(M):
        u, v, distance = map(int, input().split())
        
        graph[u].append((distance, v))

    total_distances = [0] * (N+1)

    for home in range(1, N+1):
        if home == party_place: continue
        total_distances[home] += get_shortest_way_from_start(party_place, home)
        total_distances[home] += get_shortest_way_from_start(home, party_place)

    print(max(total_distances))