목록2024/09/03 (2)
공부 기록장
https://www.acmicpc.net/problem/1238 코드# 다익스트라 두 번 쓰는 풀이import heapqINF = int(1e9)def dijkstra(start): distance = [INF] * (N+1) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: dist, now = heapq.heappop(q) if distance[now] 접근 방법- 플로이드 워셜로 풀면 되겠다고 생각했지만 시간 초과- N이 최대값인 경우 10억번의 연산이 필요하게 되고, 시간 초과 발생- 다익스트라를 2번 사용하는 풀이 참고 배운 점- 플로이드 워셜을 복습할 수 있었다- 다익스트..
https://www.acmicpc.net/problem/1916 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)n = int(input())m = int(input())graph = [[] for _ in range(n+1)]distance = [INF] * (n+1)for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c))start, end = map(int, input().split())def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 ..