힙2 [백준 1238번] 파티 문제 풀이 먼저 간단한 다익스트라 구조를 이용하여 가는 거리와 오는 거리를 구해 최댓값을 구했는데, 입출력은 동일하나 시간 초과가 나왔다. 그래서, 힙을 이용하여 개선된 다익스트라 알고리즘을 사용하였더니 해결되었다. import sys import heapq input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m, x = map(int, input().split()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range(n +1)] # 모든 간선 정보를 입력 받기 for _ in range(m): a, b, c = map(int ,input().split()) # a번 노드에서 b번.. 2023. 8. 8. [개념] 다익스트라 알고리즘 간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가진다. ( V는 노드의 개수 ) ✔ 방법 1 import sys input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력 받기 start = int(input()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range(n+1)] # 방문한 적이 있는지 체크하는 목적의 리스트 만들기 visited = [False] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # 모든 간선 정보를 입력.. 2023. 8. 3. 이전 1 다음
