MathTrauma

출발, 도착 지점과 대포들이 놓인 지점들을 정점으로 두고 각 정점들 사이의 이동시간을 가중치로 두면, 일반적인 최소 비용 문제(최단 경로 문제)가 된다. 대포를 이용해서 이동하거나 도보로 가거나 두 가지 선택지 있다. 위의 정보로부터 대포의 위치가 아닌 시작 정점을 제외한 정점에서 다른 정점을 잇는 간선의 가중치는 \[ time= \min( distance/5. \; , 2+|distance-50|/5.) \] 로 두면 된다. 시작 정점에서 다른 정점까지 가중치는 \[time = distance/5. \] 으로 둔다. (대포의 위치가 시작 위치와 겹쳐도 위의 식들은 유효하다. 0 시간을 이동해서 대포로 이동하는 상황이 될 것이다.) #include using namespace std; const doub..