최단경로 (3) 썸네일형 리스트형 백준 2176 - 합리적인 이동경로 www.acmicpc.net/problem/2176 솔루션 1. 더보기 모든 정점 사이의 최단 경로를 구한 다음 그래프 DP를 수행하면서 "합리적인 이동경로"를 탐색하면 간단하게 AC를 받을 수 있다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include using namespace std; usi.. 백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ .. 백준 11779 - 최소비용 구하기 2 http://icpc.me/11779 출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다. 하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다. 알아야 할 것 최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다. 우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다. 이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다. 구현 최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후, 저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다. 전체 코드 더보기 #include using namespace std; using ll = long lo.. 이전 1 다음
