[BOJ]5719번: 거의 최단 경로

 

문제: https://www.acmicpc.net/problem/5719

---

jaimemin님 블로그의 솔루션을 참고해서 해결했습니다. (https://jaimemin.tistory.com/617)

 

 

다익스트라를 진행하게 되면 src => dst 방향으로 최종 노드까지 최소 간선비용으로 갱신이 됩니다.

 

이 점을 이용해서 다익스트라 진행 중,

 

최소 간선 비용이거나, 최소 간선 비용과 비용이 같은 경우 before라는 벡터를 선언해 저장해줍니다.

 

//before[NODE]: 최소 간선 비용으로 정점 NODE로 들어오는 정점들을 저장한 벡터
//ex. before[NODE] = {1,2,3,4} 이면
// 1번 정점 => NODE, 2번 정점 => NODE, 3번 정점 => NODE, 4번 정점 => NODE

vector<int> before[NODE_SIZE];

before[dst].push_back(src);

 

풀이 과정은 다음과 같습니다.

 

1. 다익스트라를 1회 돌리면서 before 벡터 만들기

 

2. BFS를 돌려서 before벡터 내(최소 비용 경로 상에 있는 모든 정점) 간선을 -1로 갱신해줍니다.

(이게 가능한 것은 문제의 조건 중 정점과 정점을 연결하는 간선이 단 한 개이기 때문입니다.)

 

3. 2번에 의해 -1로 갱신된 간선들을 제외하고 다익스트라를 한 번 더 돌리면 거의 최단 경로가 완성됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ5719.cc