[C/C++] 백준 1504번 - 특정한 최단 경로

✏️ 문제 링크

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

✏️ 문제 설명

✏️ 문제 풀이

다익스트라 알고리즘을 적용시켜서 풀었습니다.

다만 두 정점을 거쳐가야 하는 최단경로를 출력해야 하므로 다음과 같은 경우의 수로 나뉘었습니다.

두 정점을 A,B라 하고 시작점을1, 도착점을 N이라고 하면

● 1 -> A -> B -> N

● 1 -> B -> A -> N

● 1 -> B -> A -> B -> N (A에서 N으로 가는 경로가 없을 때)

● 1 -> A -> B -> A -> N ( B에서 N으로 가는 경로가 없을 때)

 

이렇게 되면 다익스트라를 총 3번 돌려야 합니다.

1을 출발점으로 다익스트라 돌리기 : 1->A의 최단경로와 1->B의 최단경로값을 알 수 있습니다.

N을 출발점으로 다익스트라 돌리기 : N->A의 최단경로와 N->B의 최단경로값을 알 수 있습니다.

A를 출발점으로 다익스트라 돌리기 : A->B의 최단경로를 알 수 있습니다.

✏️ 문제 코드

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

#define INF INT_MAX
typedef pair<int, int> cur;
priority_queue <cur, vector<cur>, greater<cur>> pq;
vector<vector<cur>> V(801);
vector<int> Res(801), Visit(801);
int N, M, A, B, C, i, idx, tmp, a, b, c, d, e;
int Ans;
bool Chk1, Chk2 , Chk3;

void Dijkstra(int start) {
    fill(Res.begin(), Res.end(), INF);
    fill(Visit.begin(), Visit.end(), 0);
    Res[start] = 0;
    pq.push({ 0,start });

    while (!pq.empty()) {
        idx = pq.top().second;
        pq.pop();
        if (Visit[idx]) continue;
        else Visit[idx]++;

        for (i = 0; i < V[idx].size(); i++) {
            C = V[idx][i].first;
            if (!Visit[C]) {
                tmp = Res[idx] + V[idx][i].second;
                if (tmp < Res[C]) {
                    Res[C] = tmp;
                    pq.push({ Res[C],C });
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        V[A].push_back({ B,C });
        V[B].push_back({ A,C });
    }

    cin >> A >> B;

    Dijkstra(1);
    if (Res[A] == INF && Res[B] == INF)
        Chk1 = true;
    a = Res[A]; b = Res[B];

    Dijkstra(N);
    if (Res[A] == INF && Res[B] == INF)
        Chk2 = true;
    d = Res[A]; e = Res[B];

    Dijkstra(A);
    if (Res[B] == INF)
        Chk3 = true;
    c = Res[B];

    Ans = min(min(a + c + e, b + c + d), min(a + c + c + d, a + c + c + e));
    
    if (Chk1 || Chk2 || Chk3)
        Ans = -1;

    cout << Ans;
}

 

 

✏️ 참고하기

https://pooreumjung.tistory.com/299

Algorithm 공부 #16 - 그래프(다익스트라 알고리즘)