이것저것 기록 블로그

import heapq INF = int(1e9) def dijkstra(N, start, graph): distance = [INF] * (N+1) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: cost, dest = heapq.heappop(q) if distance[dest] tmp: distance[d] = tmp heapq.heappush(q, (tmp, d)) return distance def solution(N, road, K): answer = 0 graph = [[] for _ in r..

import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m, x = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b,c)) def dijkstra(start): distance = [INF] * (n+1) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: cost, dest = heapq.heappop(q) if distance[dest] < cost: continue for d, c..

어느 정점을 들르는 경우는 전부 플로이드-워셜로 푸는 줄 알았다.. 그러나 플로이드-워셜은 기본적으로 O(N^3)의 시간 복잡도를 갖기 때문에 간선이나 정점이 500개 이상인 문제에서는 거의 다 시간초과로 걸려버린다. INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n+1) for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = c graph[b][a] = c for i in range(1, n+1): for j in range(1, n+1): if i == j: graph[i][j] = 0 #print(graph) for k in..

import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start = 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)) q = [] distance[start] = 0 heapq.heappush(q, (0, start)) while q: cost, dist = heapq.heappop(q) if distance[dist] < cost: continue for i in gr..