KBW's cosmos

처음에는 플로이드로 풀었다. """ 1. 아이디어 - 플로이드로 전체 마을 사이의 최단 경로를 구한다. - 이중 for문으로 도로의 길이의 합이 가장 작은 사이클을 찾는다. 2. 시간 복잡도 - O(V^3 + V^2) : 400 ^ 3 ~= 6억 3. 변수 - V, E : int - dist : int[][] - min_dist : int """ import sys INF = sys.maxsize input = sys.stdin.readline V, E = map(int, input().split()) dist = [[INF] * (V + 1) for _ in range(V + 1)] for l in range(1, V + 1): dist[l][l] = 0 for _ in range(E): a, b, c..

""" 1. 아이디어 - 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간 -> 다익스트라 2. 시간 복잡도 - O(ElgV) : 6000 * lg(500) ~= 16000 -> 가능 3. 변수 - N, M : int - 인접 리스트 : (이동 시간, 도착 도시)[][] - 최단 거리 배열 : int[] - 갈 수 있는 도시들 : heap """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) edge = [[] for _ in range(N + 1)] for _ in range(M): A, B, C = map(int, input().split()) edge[A]..

""" 1. 아이디어 - 우선 반드시 지나야 하는 두 정점 사이의 최소 거리를 구한다. (다익스트라) - 그리고 1번 정점과 v1, v2 / N번 정점과 v1, v2 사이의 거리를 구한 뒤 더 짧은 거리를 선택한다. 2. 시간 복잡도 - O(3 * ElgV) = 5 * 200000 * lg(800) =~ 2,903,089 -> 가능 3. 변수 - 정점의 개수, 간선의 개수 : int - 힙 : (비용, 노드번호) - 거리배열 : int[] - 인접 간선 리스트 : (비용, 노드번호)[] """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, E = map(int, input().split()) edge = [[] for _ ..

""" 1. 아이디어 - 한점 시작, 모든 거리 : 다익스트라 - 간선, 인접리스트 저장 - 거리배열 무한대 초기화 - 시작점 : 거리배열 0, heap에 넣어주기 - 힙에서 빼면서 다음의 것들 수행 - 최신값인지 먼저 확인 - 간선을 타고 간 비용이 더 작으면 갱신 2. 시간복잡도 - 다익스트라 : O(ElgV) - E : 3e5 (문제에서 1