1504번 - 특정한 최단 경로

1504번-특정한 최단 경로

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

1504번: 특정한 최단 경로

 

---

문제 알고리즘 분류

이 문제는 Dijkstra 알고리즘을 이용하는 문제이다.

다익스트라 개념을 아시는 분들이라면 충분히 활용하여 푸실 수 있을 것 이다.

 

다익스트라 개념 바로가기 -> https://yhoons.tistory.com/4

다익스트라 알고리즘(Dijkstra algorithm) - c++

 

---

문제 아이디어

 

이 문제는 어떻게 두 정점을 무조건 지나게 하는 지를 생각해보는 게 핵심인 것 같다.

 

반드시 거쳐야하는 두 정점 v1,v2를 과연 어떻게 거쳐야 할까?

 

거쳐야하는 정점이 2개라고 정의가 돼있으니까 우린 간단하게 생각할 수 있다.

첫 번째 노드에서 반드시 거쳐야하는 노드까지의 최단 거리 + 반드시 거쳐야하는 노드에서 마지막 N 번째 노드까지의 최단 거리를 구하면 되지 않을까??

 

이는 즉,

1. 1 -> v1 -> v2 -> N

2. 1 -> v2 -> v1 -> N

로 표현 할 수 있다.

 

v1과 v2의 위치는 서로 다르기 때문에 두 가지의 경우의 수가 나온다.

두 값을 구한 후 값이 더 작은 것을 선택해주면 된다.

 

또 하나 주의해야할 점은 예외 처리이다.

문제에서 보면 경로가 없을 때 -1을 출력하라고 한다.

경로가 없다는 뜻은 거리에 대한 정보가 처음 초기화 해줬던 INF값이 그대로 들어있을 것이므로

1부터 N까지의 거리가 INF보다 크거나 같으면 어느 한 부분이라도 경로가 없다는 뜻이다.

 

따라서 그 부분만 조심해서 예외처리를 해주면 문제없이 맞출 수 있을 것이다.

#include<iostream>
#include<vector>
#include<queue>
#define INF 1000000001
using namespace std;


vector<pair<int, int> > v[801]; //노드 간 정보를 저장하기 위한 벡터 배열
int d[801] = {0,}; //출발노드와의 거리를 저장하는 배열


void dijkstra (int n) { //다익스트라 알고리즘
    for(int i=1; i<=800; i++) {
        d[i] = INF;
    }
    d[n] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(n,0));

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

        if(d[currentnode] < distance)
            continue;

        for(int i=0; i<v[currentnode].size(); i++) {
            int next = v[currentnode][i].first;
            int nextdistance = distance + v[currentnode][i].second;
            if(nextdistance < d[next]) {
                d[next] = nextdistance;
                pq.push(make_pair(next, -nextdistance));
            }
        }
    }
}


int func(int vone, int vtwo, int n) { //1->v1->v2->N 거리를 구하는 함수
    double a=0; //double로 한 이유는 해당 경로가 없을 때 초깃값 무수히 큰 값(INF)이 더해지기 때문
    dijkstra(1); //1을 출발 노드로 지정
    a += d[vone]; //1->v1 거리를 a에 더함
    dijkstra(vone); //v1을 출발 노드로 지정
    a += d[vtwo]; //v1->v2 거리를 a에 더함
    dijkstra(vtwo); //v2를 출발 노드로 지정
    a+=d[n]; //v2->N 거리를 a에 더함

    if(a>=INF) //즉 해당 경로가 하나라도 없다면
        return -1;
    else
        return a;
}


int main() {
    int N,E,a,b,c; //N:정점의 개수, E: 간선의 개수, a,b,c: 세 개의 정수
    int result[2] ={0,}; //비교할 경로를 저장할 배열

    cin >> N >> E;
    for(int i=0; i<E; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    
    int v1, v2; //꼭 지나야 하는 정점
    cin >> v1 >> v2;

    result[0] = func(v1,v2,N);
    result[1] = func(v2,v1,N);

    if(result[0]<result[1])
        cout << result[0];
    else
        cout << result[1];
}