다익스트라

[Python] 백준 4485 녹색 옷 입은 애가 젤다지? | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해결 포인트 - 다익스트라를 이용하여 각 위치별 (0, 0)에서 최소 비용을 계산 - dr, dc : 각 위치에서 아래, 위, 오른쪽, 왼쪽 위치를 방문 하기 위한 방향키 - graph : 각 위치 방문을 위해 필요한 비용 - distance : 각 위치에서 (0, 0)까지 가기위한 최소 비용, 초기는 무한수 작성 코드 imp..

[Python] 백준 1504 특정한 최단 경로 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 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 문제 해결 포인트 - v1 -> v2 순서 또는 v2 -> v1 순서 각각의 거리를 구하여 작은 값을 출력한다. (2번의 다익스트라) - 경로가 없는 경우(결과 값이 INF보다 크거나 같은 경우) -1을 출력 자세한 내용은 코드 주석 참고 작성 코드 import sys import heapq input =..