algospot 음주 운전 단속 (문제 ID: DRUNKEN) c++

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

algospot.com :: DRUNKEN

각 장소마다 음주운전을 할때의 소요시간이 있고 장소에서 다른 장소로 옮길때에도 소요시간이 있다.

시작 장소에서 약속 장소로 이동하는 경로 중, 최악의 예상 시간이 가장 작은 경로를 찾는것이 문제이다.

여기서 최악의 예상시간이란 경로중에 단속시간이 제일 긴 장소에서 음주단속이 걸렸을때를 말한다.

 

단속시간이 작은 장소를 우선적으로 경유하게끔 플로이드 알고리즘을 변형시켜 사용하면 문제를 해결할 수 있다.

Ck(u, v)를 k 혹은 그보다 단속 시간이 적게 걸리는 정점들만을 경유해서 u에서 v로 가는 최단거리라 했을때

최악의 예상시간은 min(Cw(u, w) + Cw(w, v) + E[w]) 라고 할 수 있다.

 

 

 

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

GitHub - sbl133/JongmanBook

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

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