1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 그러나 주의할 점이 있었는데 바로 꼭 거쳐야하는 2개의 지점이 있다는것 입니다. 지나가야 하는 지점이 x, y라 할 경우
1 -> x -> y -> N
1 -> y -> x -> N
이렇게 두가지의 경우가 있으므로 위의 두가지 경우에 대한 다익스트라 알고리즘을 적용하여 거리를 각각 구한 후 더 작은 숫자를 출력하면 됩니다. 또한 문제에서 이동할 수 없는 거리라면 -1을 출력하라는 조건이 있었기 때문에 이를 유의하여 해결합니다.
소스코드
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 36 37 38 39 40 41 42 43 | import heapq INF = 1001 n, m = map(int, input().split()) graph = [[] for _ in range(1 + n)] for i in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c)) graph[b].append((a, c)) def dijkstra(start, pos): distance = [INF] * (1 + n) q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) return distance[pos] x, y = map(int, input().split()) dist1 = dijkstra(1, x) dist2 = dijkstra(x, y) dist3 = dijkstra(y, n) dist4 = dijkstra(1, y) dist5 = dijkstra(y, x) dist6 = dijkstra(x, n) ans = min(dist1 + dist2 + dist3, dist4 + dist5 + dist6) if ans >= INF: print(-1) else: print(ans) | cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1463번: 1로 만들기 (Python) (0) | 2021.12.27 |
|---|---|
| 백준 알고리즘 13549: 숨바꼭질 3(Python) (0) | 2021.02.25 |
| 백준 알고리즘 1068: 트리(Python) (0) | 2021.02.21 |
| 백준 알고리즘 1074: Z(Python) (0) | 2021.02.20 |
| 백준 알고리즘 13459: 구슬 탈출(Python) (0) | 2021.02.19 |