문제 링크 http://icpc.me/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 다익스트라를 이용하여 풀 수 있다. 모든 점에 대해서 다익스트라를 돌려서 O(M^2logN)에도 풀 수 있지만, 관점을 약간 틀면 더 O(MlogN)에 풀 수 있다. 단방향 도로이기 때문에 순방향으로 x를 시작점으로 돌린다면 마을로 돌아가는 최간거리를 구할 수 있다. 그리고 역방향그래프를 x를 시작점으로 돌린다면 x까지 가는 최단거리를 구할 수 있다. 코드 #include usin..

문제 링크 http://icpc.me/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라를 두 번 돌려서 풀 수 있다. 최단 경로로 오기 위한 모든 경로를 처음 다익스트라를 돌릴 때 prv 벡터에 어디서 온 건지 저장해놓는다. 이때 dist 값이 변경될 때 이차원 벡터를 초기화하고 그 벡터에 넣는 방식으로 구현했다. 그런 후 dfs를 통해 최단 경로들을 모두 없앤다. 이때 중복되는 dfs를 제거하지 않으면 최대 재귀 호출을 10^4만큼 시간 초과가 발생한다...