본문 바로가기
728x90
반응형

다익스트라

Algorithm & Data Structure 2022. 8. 18. 백준 - 1956번(다익스트라) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys from heapq import heappush,heappop v,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(v+1)] ans = [[float('inf') for _ in range(v + 1)] for _ in range(v+1)] q = [] for _ in ra..
Algorithm & Data Structure 2022. 8. 6. 백준 - 9370번(다익스트라, DP) https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import sys from collections import deque def dajik(st, ed): if st == ed: return 0 q = deque([]) q.append([0, st]) dist = [float('inf')] * (n + 1) while q: now_value, st = q.popleft() for i in arr[st]: if now_value + i[1]..
Algorithm & Data Structure 2022. 8. 6. 백준 - 1504번(다익스트라, DP) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import sys import heapq n,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(n+1)] for _ in range(e): a,b,c = map(int,sys.stdin.readline().split()) arr[a].append([b,c]) arr[b].append..
Algorithm & Data Structure 2022. 5. 22. 백준 - 1753번(다익스트라,우선순위 큐) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net import sys import heapq v, e = map(int, sys.stdin.readline().split()) s = int(sys.stdin.readline()) arr = [[] for _ in range(v + 1)] ans = [float('INF') for _ in range(v + 1)] for _ in range(e): a, b, c..
Algorithm & Data Structure 2022. 5. 21. 백준 - 1446번(다익스트라, DP) https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net import sys n,d = map(int,sys.stdin.readline().split()) arr = [] for i in range(n): arr.append(list(map(int,sys.stdin.readline().split()))) arr.sort(key= lambda x:(x[0],x[1],x[2])) ans = [i for i in range(d+1)] for i i..
Algorithm & Data Structure 2022. 5. 21. 백준 - 18352번(다익스트라, BFS) https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import sys from collections import deque n,m,k,x = map(int,sys.stdin.readline().split()) arr = [[]for _ in range(n+1)] for i in range(m): a,b = map(int,sys.stdin.readline().split()) ..
728x90
반응형

티스토리툴바