반응형
알고리즘 분류 : 다익스트라
1부터 출발해서 정점 X와 Y를 모두 거쳐서 N에 도착하는 최단 거리를 구하는 문제다. 이동 거리가 1 이상의 값을 가지므로, 다익스트라를 이용해야 한다. 정점 두 군데를 모두 거쳐야 하므로, 다익스트라를 여러 번 호출해야 한다. 다익스트라를 여러 번 호출해야 하므로, dist 배열을 매번 INF로 초기화해야 하는 것에 유의한다.
- 방향성이 없는 그래프이므로, 입력받을 때 양방향으로 저장한다.
- X, Y를 모두 거쳐서 도착하는 방법은 2가지가 존재한다. 1 → X → Y → N 와 1 → Y → X → N 이다.
- 1 → X, X → Y, Y → N으로 가는 방법을 경로 1이라 하고, 그 이동 거리를 저장한다.
- 1 → Y, Y → X, X → N으로 가는 방법을 경로 2라 하고, 그 이동 거리를 저장한다.
- 경로 1과 경로 2를 비교하여 작은 값을 출력하고, 그 값이 만약 INF를 넘어선다면 -1을 출력하면 된다.
C++ 소스코드
#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; struct graph { int node, cost; bool operator < (const graph t) const { return cost > t.cost; } }; int n, m, x, y; const int INF = 1e9; int dijkstra(vector<graph> v[], int dist[], int depart, int arrive) { priority_queue<graph> pq; pq.push({depart, 0}); fill(dist, dist+n, INF); dist[depart] = 0; while (!pq.empty()) { int now = pq.top().node, cost = pq.top().cost; pq.pop(); if (dist[now] < cost) continue; for (auto k : v[now]) { int next = k.node, ncost = cost+k.cost; if (dist[next] > ncost) { dist[next] = ncost; pq.push({next, ncost}); } } } return dist[arrive]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; vector<graph> v[n]; int dist[n]; while (m--) { int a, b, c; cin >> a >> b >> c; v[a-1].push_back({b-1, c}); v[b-1].push_back({a-1, c}); } cin >> x >> y; // 1 → X → Y → N int path1 = dijkstra(v, dist, 0, x-1) + dijkstra(v, dist, x-1, y-1) + dijkstra(v, dist, y-1, n-1); // 1 → Y → X → N int path2 = dijkstra(v, dist, 0, y-1) + dijkstra(v, dist, y-1, x-1) + dijkstra(v, dist, x-1, n-1); // Print minimum distance or print -1 if not exsit. if (path1 < path2 && path1 < INF) cout << path1 << '\n'; else if (path1 > path2 && path2 < INF) cout << path2 << '\n'; else cout << "-1\n"; return 0; }
Python 3 소스코드
from heapq import heappush, heappop from sys import stdin input = stdin.readline INF = 1e9 n, m = map(int, input().split()) v = [[] for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) v[a-1].append([b-1, c]) v[b-1].append([a-1, c]) x, y = map(int, input().split()) def dijkstra(depart, arrive): dist = [INF]*n pq = [] heappush(pq, (0, depart)) dist[depart] = 0 while pq: cost, now = heappop(pq) if dist[now] < cost: continue for nxt, ncost in v[now]: ncost += cost if dist[nxt] > ncost: dist[nxt] = ncost heappush(pq, (ncost, nxt)) return dist[arrive] path1 = dijkstra(0, x-1) + dijkstra(x-1, y-1) + dijkstra(y-1, n-1) path2 = dijkstra(0, y-1) + dijkstra(y-1, x-1) + dijkstra(x-1, n-1) ans = min(path1, path2) print(ans if ans < INF else "-1")
참고
반응형