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 어떤 지점을 중심으로 가장 가까운 맥도날드나 스타벅스를 구하라면 평범한 최단 경로 문제이겠으나, 정점들 중 거리의 합이 최소가 되어야 하므로 각 정점에서 맥도날드 스타벅스까지의 최단 경로를 구하기는 곤란하다. (정점이 너무 많다.) 그래서 출발 정점을 맥도날드나 스타벅스로 두고 해결해야 할 듯하다. (이것도 많은데?) 가장 가까운..

문제 링크 : https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 문제에서 등산의 '가치' 를 (얻은 성취감) - (소모한 체력) 으로 계산 라 했는데 성취감은 중간 경로에 관계없이 도달한 지점의 높이에만 의존한다. 한편, 거리당 소모 체력을 D 라 했으니 소모한 총 체력 = D * (거리) 이므로 결국 각 지점까지의 '최단 거리' 를 구하는 문제로 환원된다. 각 지점까지 높이가 증가한 다음 높이가 감소한다는 식으로 생각하면 머리 아프다...

문제 링크 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 통상의 거리(비용)을 순서쌍 비용으로 바꾸면 된다. 즉, 거리를 pair(지나온 g의 개수, g 인접한 곳을 지난 횟수) 로 두면 평범한 최단 경로 문제가 된다. 하지만, 문제의 조건을 여러 번 잘못 읽었다. 시작, 마지막 지점은 쓰레기 옆이어도 count 하지 않는다는 조건도 한참 뒤에서야 봤다. #include using namespace std; s..

제공되는 priority queue 를 사용하는 대신 Min Heap 을 직접 구현해서 최단 경로 문제를 풀어보았다. 문제 링크 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net pos 배열은 정점의 번호를 heap 내부의 위치로 바꾸어 준다. x=pos[id]; 이 코드는 id 정점이 heap 의 x 위치에 해당된다는 뜻이다. pos 에 대해 일종의 역함수인 rev 배열은 heap 의 위치에 대응되는 정점의..