Dijkstra algorithm (2) 썸네일형 리스트형 백준 11779 - 최소비용 구하기 2 http://icpc.me/11779 출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다. 하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다. 알아야 할 것 최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다. 우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다. 이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다. 구현 최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후, 저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다. 전체 코드 더보기 #include using namespace std; using ll = long lo.. [ICPC] 백준 5719 - 거의 최단 경로 http://icpc.me/5719 Step 1. 최단 경로를 구해보자. 다익스트라를 통해 어렵지 않게 구할 수 있다. 만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자. 노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자. 다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자. Step 2. 도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다. 올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경.. 이전 1 다음
