백준 17381 1738. 골목길 (Swift, Python) https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 풀이 민승이네 집(1번)에서 코레스코 콘도(n번)까지 가는데 있어서 최적의 경로를 찾는 문제이다. 가는 경로에 음수가 존재하므로 다익스트라 알고리즘으로는 해결할 수 없고 벨만 포드 알고리즘을 이용해서 해결 가능하다. 기존과의 차이점은 보통 목적지까지 최단 거리를 찾는거였다면 이번 문제는 금품의 양이 최대가 되는 경로를 찾는 것이다. 하나 주의할 건 기존의 벨만 포드 알고리즘.. 2021. 11. 18. 이전 1 다음
