728x90 백준17381 [파이썬] 1738 골목길 (백준) 1. 문제 설명 문제 : 1738 - 골목길 https://www.acmicpc.net/problem/1738 사용 언어 : 파이썬 (Pypy3) 문제요약 : 각 거리마다 얻거나, 빼앗길 수 있는 금품의 양이 주어졌을 때, 최대의 금품을 갖게 될 수 있는 경로를 구하여라. 알고리즘 : 벨만-포드 2. 문제 풀이 해설 : 일반적인 벨만포드를 이용하여 구할 수 있다. 이때 고려해야 할 점이 몇 가지 있다. 1. 최소 가중치를 찾는 벨만포드와는 다르게, 최대 가중치를 구해야 하므로 distance를 -inf로 초기화해야 한다. (이에 따라 조건식을 조금 바꾸어야 한다.) 2. 중요한 경로 구하기!! 각 노드마다 그 전의 노드를 구해놓아 마지막에 최단 경로를 구한다. 코드 : import sys; input =.. 2023. 12. 31. 이전 1 다음 728x90
