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

 

algospot.com :: DRUNKEN

Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day,

algospot.com

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

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

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

 

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

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

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

+ Recent posts