본문 바로가기

Programming/BOJ

BOJ 1504 · 특정한 최단 경로


알고리즘 분류 : 다익스트라  


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")




참고



태그