본문 바로가기
728x90
반응형

최단경로

Algorithm & Data Structure 2022. 11. 2. 백준 - 11404번(플로이드) https://www.acmicpc.net/problem/11404 import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) arr = [[float('INF') for _ in range(n)] for _ in range(n)] bus = [] for i in range(n): arr[i][i] = 0 for _ in range(m): a,b,c = map(int,sys.stdin.readline().split()) if arr[a-1][b-1] > c: arr[a-1][b-1] = c for k in range(n): for i in range(n): for j in range(n): if arr[i][j] > arr[i][k] +..
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. 백준 - 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..
728x90
반응형

티스토리툴바