[BOJ] Q1238 파티

[BOJ] Q1238 파티

Question

Language: Python

Difficulty: Gold 3

모든 사람에 대해서 특정 위치에 대한 왕복거리를 구하는 문제이다. 모든 사람이니까? floyd-warshall로 풀면 되지 않을까? –> 문제에 주어진 조건을 보면 노드 개수가 1000개이다. 즉, 1000³ 번의 연산을 수행하게 되는데 그러면 시간 초과가 발생하게 된다. 따라서 해당 문제는 dijkstra를 이용해서 문제를 풀어야 한다.

모든 사람에 대해서 dijkstra를 수행한 후, dijkstra 수행 결과를 이차원 리스트에 저장해서 각각의 사람에 대해서 왕복거리를 비교한다.

Solution

import heapq
from math import inf

def dijkstra(start):
    distance=[inf] * (v+1)
    distance[start]=0

    heap=[(0,start)]

    while heap:
        cost,vertex=heapq.heappop(heap)

        if cost>distance[vertex]:
            continue
            
        for adj_vertex,weight in graph[vertex]:
            cost=distance[vertex]+weight
            if distance[adj_vertex] > cost:
                distance[adj_vertex]=cost
                heapq.heappush(heap,(cost,adj_vertex))
    return distance

def solution():
    for i in range(1,v+1):
        distances.append(dijkstra(i))

    max_cost=0

    for i in range(1,v+1):
        max_cost=max(max_cost,distances[i][end]+distances[end][i])
    return max_cost
    
if __name__ == "__main__":
    v,e,end=map(int,input().split())
    graph=[[] for _ in range(v+1)]
    for _ in range(e):
        v1,v2,weight=map(int,input().split())
        graph[v1].append((v2,weight))
    distances=[[]]
    print(solution())