MathTrauma

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

문제 링크 : https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 어떤 지점을 중심으로 가장 가까운 맥도날드나 스타벅스를 구하라면 평범한 최단 경로 문제이겠으나, 정점들 중 거리의 합이 최소가 되어야 하므로 각 정점에서 맥도날드 스타벅스까지의 최단 경로를 구하기는 곤란하다. (정점이 너무 많다.) 그래서 출발 정점을 맥도날드나 스타벅스로 두고 해결해야 할 듯하다. (이것도 많은데?) 가장 가까운..