[백준] 1504번 : 특정한 최단 경로

문제

 

---

풀이

 

반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는

1->B->C->N 또는 1->C->B->N일 것이다.

이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다.

 

1에 대하여 실행해 1->B, 1->C의 최단 거리를 알아야 하고

B에 대하여 실행해 B->C, B->N의 최단 거리를 알아야 하고

C에 대하여 실행해 C->B, C->N의 최단 거리를 알아야 한다.

 

N까지 가는 두가지 경로 중 작은 것을 택하면 된다.

 

다익스트라 알고리즘의 자세한 구현 설명은

myunji.tistory.com/344

[백준] 1753번 : 최단경로

여기에 있다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

const int INF = 1e6; //INF이 최대 3번 더해질 수 있음
typedef pair<int, int> pp;

vector<vector<pp>> graph; //graph[i][j].first = dest, graph[i][j].second = weight
vector<int> V_dist; //INF로 초기화
vector<bool> visited; //방문 체크
priority_queue<pp, vector<pp>, greater<pp>> min_dist; //min-heap, min_dist.first = distance, min_dist.second = source

void dijkstra(int start) {
    int new_dist;

    V_dist[start] = 0; //시작점의 거리는 0
    min_dist.push(make_pair(V_dist[start], start)); //거리와 source 투입

    while (!min_dist.empty()) { //우선순위 큐가 비어있지 않을 때
        int dist = min_dist.top().first; //현재 노드 까지의 최단 거리
        int source = min_dist.top().second; //노드
        min_dist.pop();

        if (!visited[source]) { //방문한 적 없는 노드라면
            for (int i = 0; i < graph[source].size(); i++) { //해당 노드가 source인 모든 정점(dest)
                new_dist = dist + graph[source][i].second; //현재 노드까지의 최단거리 + source에서 dest까지의 weight
                if (new_dist < V_dist[graph[source][i].first]) { //이 값이 기존의 V_dist[dest]보다 작다면
                    V_dist[graph[source][i].first] = new_dist; //dest의 최단거리 갱신
                    min_dist.push(make_pair(new_dist, graph[source][i].first)); //우선순위 큐에 거리와 dest 노드 정보 삽입
                }
            }
        }
        visited[source] = true; //source 노드 방문 처리
    }
}

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

    int N, E, a, b, c, v[3];
    vector<vector<int>> s_dist;

    cin >> N >> E;
    graph.assign(N + 1, vector<pp>(0));
    s_dist.assign(N + 1, vector<int>(N + 1));
    for (int i = 0; i < E; i++) { //양방향
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    v[0] = 1;
    cin >> v[1] >> v[2];
    for (int i = 0; i < 3; i++) { //다익스트라 3회
        V_dist.assign(N + 1, INF);
        visited.assign(N + 1, false);

        dijkstra(v[i]);
        for (int j = 1; j <= N; j++)
            s_dist[v[i]][j] = V_dist[j];
    }

    int result = min(s_dist[v[0]][v[1]] + s_dist[v[1]][v[2]] + s_dist[v[2]][N], //A->B->C->D
                     s_dist[v[0]][v[2]] + s_dist[v[2]][v[1]] + s_dist[v[1]][N]); //A->C->B->D
    if (result >= INF)
        cout << -1;
    else
        cout << result;
}

전체 소스코드다. 1753과 다른 부분만 설명하겠다.

 

    v[0] = 1;
    cin >> v[1] >> v[2];
    for (int i = 0; i < 3; i++) { //다익스트라 3회
        V_dist.assign(N + 1, INF);
        visited.assign(N + 1, false);

        dijkstra(v[i]);
        for (int j = 1; j <= N; j++)
            s_dist[v[i]][j] = V_dist[j];
    }

v배열에 다익스트라를 실행해야 하는 정점을 저장한다. 시작 정점인 1과 입력으로 주어지는 2개의 값이다.

그리고 다익스트라를 실행해 얻은 v[i]로부터의 최단 거리를 s_dist라는 2차원 벡터에 저장한다.

 

s_dist[i][j]에는 i에서 j로 가는 최단 거리가 저장됐을 것이다.

 

    int result = min(s_dist[v[0]][v[1]] + s_dist[v[1]][v[2]] + s_dist[v[2]][N], //A->B->C->D
                     s_dist[v[0]][v[2]] + s_dist[v[2]][v[1]] + s_dist[v[1]][N]); //A->C->B->D

그리고 좀 노가다성이 짙어보이지만 이렇게 계산해서 최솟값을 비교한다.

 

    if (result >= INF)
        cout << -1;
    else
        cout << result;

최솟값이 INF 이상이었다면 경로가 없었단 뜻이니 -1을 출력한다.