백준 1504번 특정한 최단 경로 (C++)

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

1504번: 특정한 최단 경로

이 문제는 2가지 루트의 최단 거리를 각각 구하여, 그 중 가장 작은 값을 선택하면 된다.

• 1 -> T1 -> T2 -> N
• 1 -> T2 -> T1 -> N

이때 경로가 없는 루트일 경우, 적절히 최대 값을 셋팅하여 Stack over flow가 발생하지 않도록 주의해야한다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수를 선언하고 값을 입력 받는다.

최단 거리를 저장하는 dist벡터와 간선을 저장하는 v벡터의 경우, 나는 필요한 크기만큼 동적할당을 해주었다.

    int a,b,c;
    cin >> n >> e;
    dist.resize(n+1,MAX);
    v.resize(n+1, vector<pair<int,int>>(n+1));
    for(int i=0; i<e; i++){
        cin >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    cin >> t1 >> t2;

2. 다익스트라 알고리즘을 통해 1번 노트부터 n번 노드까지의 최단거리를 구한다. 코드는 아래와 같다.

    dijk(1); // main함수
    ...
    
    
void dijk(int start){
    int pos, dis, next, ndis;
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
    for(int i=1; i<=n; i++) dist[i] = MAX; // 1
    q.push({start,0}); // 2
    dist[start] = 0; // 3
    while(!q.empty()){
        pos = q.top().first;
        dis = q.top().second;
        q.pop();
        for(int i=0; i<v[pos].size(); i++){ // 4
            next = v[pos][i].first;
            ndis = v[pos][i].second;
            if(dist[next]>dist[pos]+ndis){
                dist[next] = dist[pos]+ndis;
                q.push({next,dist[next]});
            }
        }
    }
}

(1) 이 다익스트라 알고리즘은 앞으로 T1과 T2를 거쳐가는 최단 거리를 구하기 위해 몇 차례 더 사용될 예정이다. 때문에 해당 함수를 호출할때마다 모든 최단 거리 값을 MAX로 설정해야한다. (MAX는 2e9로 선언했다.)

(2) 현재 시작지점과 누적 이동 거리를 큐에 삽입해준다.

(3) 현재 시작지점의 최단거리는 0으로 설정해준다.

(4) 다익스트라 알고리즘을 통해 시작지점부터 각 노드까지의 최단거리를 갱신해준다.

 

3. 다음은 A와 B를 거쳐가는 두 가지 루트의 최단거리를 구하기 위한 twoTrack 함수이다.

    two_Track(); // main함수
    ...
    void twoTrack(){
        int a1,a2,b1,b2;
        temp1 = dist[t1]; // 1
        temp2 = dist[t2]; // 2
        dijk(t1); // 3
        a1 = dist[t2]; // 4 - 양방향
        b1 = dist[t2]; // 5 - 양방향
        b2 = dist[n]; // 6
        dijk(t2); // 7
        a2 = dist[n]; // 8
        temp1 = min(ans,temp1+a1+a2); // 9
        temp2 = min(ans,temp2+b1+b2);
        ans = min(temp1,temp2);
}

우리는 이미 다익스트라 알고리즘을 통해 1번 노드부터 n번 노드까지의 최단거리를 구했다.

(1) 1번 노드부터 t1노드까지의 최단 거리를 temp1에 초기화 해준다.

참고로 그냥 더 해줄 경우, 만약 없는 경로라면 MAX값을 누적해버려 stack over flow가 나올 수 있으니 주의해야한다. 

(2) 1번 노드부터 t2노드까지 최단 거리를 temp2에 초기화 해준다.

(3) t1부터 n까지의 최단거리를 구한다.

(4) a1은 t1부터 t2까지의 최단거리 값이다.

(5) b1은 t2부터 t1까지의 최단거리 값이다. 4번과 값이 같은 이유는, 결국 양방향 노드이기 때문이다.

(6) b2는 t1부터 n까지의 최단거리 값이다. 이로써 1 -> t2 -> t1 -> n까지의 최단거리는 구했다.

(7) t2부터 n까지의 최단거리를 구한다.

(8) a2는 t2부터 n까지의 최단 거리이다.

(9) 1->t1->t2->n과 1->t2->t1->n의 최단거리를 각각 구한 뒤, 최소 값을 ans에 저장해둔다.

 

4. 값을 출력한다.

    if(ans==MAX) cout << -1 << "\n";
    else cout << ans << "\n";

 

#include <iostream>
#include <algorithm>
#include <vector> 
#include <queue>
#define MAX 2e9
using namespace std;

int n,e,t1,t2;
unsigned long long temp1 = MAX, temp2 = MAX, ans = MAX;
vector<int> dist;
vector<vector<pair<int,int>>> v;

void dijk(int start){
    int pos, dis, next, ndis;
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
    for(int i=1; i<=n; i++) dist[i] = MAX;
    q.push({start,0});
    dist[start] = 0;
    while(!q.empty()){
        pos = q.top().first;
        dis = q.top().second;
        q.pop();
        for(int i=0; i<v[pos].size(); i++){
            next = v[pos][i].first;
            ndis = v[pos][i].second;
            if(dist[next]>dist[pos]+ndis){
                dist[next] = dist[pos]+ndis;
                q.push({next,dist[next]});
            }
        }
    }
}

void twoTrack(){
    int a1,a2,b1,b2;
    temp1 = dist[t1];
    temp2 = dist[t2];
    dijk(t1);
    a1 = dist[t2]; // 양방향
    b1 = dist[t2]; // 양방향
    b2 = dist[n];
    dijk(t2);
    a2 = dist[n];
    temp1 = min(ans,temp1+a1+a2);
    temp2 = min(ans,temp2+b1+b2);
    ans = min(temp1,temp2);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a,b,c;
    cin >> n >> e;
    dist.resize(n+1,MAX);
    v.resize(n+1, vector<pair<int,int>>(n+1));
    for(int i=0; i<e; i++){
        cin >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    cin >> t1 >> t2;
    dijk(1);
    twoTrack();
    if(ans==MAX) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

이 코드는 108ms가 소비되었다.