상위 99.99%의 PS

https://www.acmicpc.net/problem/5822 5822번: 악어의 지하 도시 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개 줄에는 R[i][0], R[i][1], L[i]가 주어진다. 다음 K개 줄에는 P[i]가 주어진다. (3 ≤ N ≤ 100,000, 2 ≤ M ≤ 1,000,000) www.acmicpc.net - 다익스트라? 문지기의 입장에서 생각해보자. 철수가 갈 수 있는 정점들 중, 가장 가까운 정점으로 가는 간선을 막는 것이 이득이다. 그러므로, 철수는 항상 두번째로 빠른 길로 가게 될 것이다. 다익스트라 비슷한 거를 탈출방부터 진행하면 된다. 답은 정점 0에 저장된 두 번째로 먼 길이가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net [DFS를 이용한 내 풀이] 1번 정점부터 dfs를 돌며 방문하지 않은 정점에 대해 팀의 색을 돌아가면서 입혀주었다. 그 후, 모든 간선에 대해 두 정점의 색이 같은지 확인해주었다. 파이썬으로 하니까 터져서 c++로 풀었다. [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..