백준 1504번 [특정한 최단 경로](C++) -yes6686- 티스토리

백준 문제 풀이: 1504 [특정한 최단 경로]

---

문제 링크: https://www.acmicpc.net/problem/1504

문제 설명:

1번 정점에서 N번 정점으로 이동하는 최단 경로를 구하되, 반드시 두 정점 v1과 v2를 통과해야 합니다. 가능한 경로 중 최단 거리를 출력합니다. 경로가 존재하지 않는 경우 -1을 출력합니다.

입력:

• 첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어집니다. (2 ≤ n ≤ 800, 0 ≤ m ≤ 200,000)
• 둘째 줄부터 m개의 줄에 간선의 정보 a, b, cost가 주어집니다. (1 ≤ cost ≤ 1,000)
• 마지막 줄에 반드시 거쳐야 하는 두 정점 v1과 v2가 주어집니다.

출력:

• 1번 정점에서 N번 정점으로 가는 최단 경로 중 v1과 v2를 반드시 지나는 최단 거리를 출력합니다. 불가능할 경우 -1을 출력합니다.

예시:

입력:
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

출력:
7

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;
vector<pair<int, int>> graph[801];
int dist[801];

void dijkstra(int start, int n) {
    priority_queue<pair<int, int>> pq;
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if (cost > dist[cur]) continue;

        for (auto &edge : graph[cur]) {
            int next = edge.first;
            int nextCost = edge.second;

            if (dist[next] > cost + nextCost) {
                dist[next] = cost + nextCost;
                pq.push({-dist[next], next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    int v1, v2;
    cin >> v1 >> v2;

    // 1번 정점에서 모든 정점까지 최단 거리 계산
    dijkstra(1, n);
    int dist1ToV1 = dist[v1];
    int dist1ToV2 = dist[v2];

    // v1 정점에서 모든 정점까지 최단 거리 계산
    dijkstra(v1, n);
    int distV1ToV2 = dist[v2];
    int distV1ToN = dist[n];

    // v2 정점에서 모든 정점까지 최단 거리 계산
    dijkstra(v2, n);
    int distV2ToN = dist[n];

    // 가능한 두 경로의 거리 계산
    int path1 = dist1ToV1 + distV1ToV2 + distV2ToN;
    int path2 = dist1ToV2 + distV1ToV2 + distV1ToN;

    // 결과 출력
    int result = min(path1, path2);
    if (result >= INF) {
        cout << -1 << '\n';
    } else {
        cout << result << '\n';
    }

    return 0;
}

---

코드 설명

이 코드는 다익스트라 알고리즘을 사용하여 주어진 조건에 따라 최단 경로를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 다익스트라 알고리즘을 세 번 수행하여 각 경로의 최단 거리를 계산합니다.
  • 1 → v1 → v2 → N과 1 → v2 → v1 → N 두 경로를 비교하여 최솟값을 출력합니다.
• 구현 세부사항:
  • dijkstra(start, n): 주어진 시작점에서 모든 정점까지의 최단 거리를 계산합니다.
  • dist[v]: 시작점에서 정점 v까지의 최단 거리를 저장합니다.
• 시간 복잡도 분석:
  • 다익스트라 알고리즘: O((n + m) log n)
  • 세 번 다익스트라 실행: O(3 * (n + m) log n)
  • 전체 시간 복잡도: O((n + m) log n)

---

결과

코드는 주어진 조건을 만족하며 최단 경로를 효율적으로 계산합니다. 두 경로의 합을 비교하여 결과를 출력합니다. 입력 크기 제한 내에서 적절히 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!