algospot 선거 공약 (문제 ID: PROMISES) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PROMISES

algospot.com :: PROMISES

도시를 연결하는 고속도로들이 있다. 추가적인 고속도로 건설 계획에서 입력순서대로 고속도로를 건설한다 했을때

고속도로 건설의 정당성은 기존에 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결되거나, 두 도시를 오가는 데 걸리는 시간이 단축되는것, 둘 중 하나라도 만족해야 한다.

이때 정당성이 없는 고속도록 건설 계획의 개수를 구하는것이 문제이다.

 

경유할 수 있는 정점의 목록을 늘려가는 기존의 플로이드 알고리즘을 간선의 목록을 늘려가는 방식으로 변형하면 문제를 해결할 수 있다.

먼저 기존의 플로이드 알고리즘을 이용하여 이미 존재하는 고속도로들만을 이용한 최단경로를 계산한다.

그 후 입력 순서대로 건설 예정인 고속도로를 추가하는 앞에서 언급한 변형된 플로이드 알고리즘을 사용하여 최단거리 갱신 유무를 확인한 후 갱신 가능하다면 최단거리를 갱신한다.

이때 주의할점은 어느 방향으로 간선을 타고 갈 것인가를 정해야하기 때문에 정점을 추가할때와는 달리 경우의 수가 3개로 늘어난다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/PROMISES.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2