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

문제 링크

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

1504번: 특정한 최단 경로

---

◆문제 해결 및 설명◆

문제 해설 : 1에서 출발해 두 개의 정점을 지나 N에 도달하는 최단 경로의 길이를 출력한다.

 

길찾기 골드4의 문제... 다익스트라다! 다익스트라는 알고 있으리라고 생각하고 설명을 해드리겠다.

우선 일반적인 다익스트라와 다른 점이라면 마지막으로 입력해준 두 개의 정점을 지나야 한다는 것이다.

이것들을 b, c라고 하고 시작과 끝의 정점을 a, b라고 했을 때 아래 사진과 같은 진행 결과가 나타난다.

따라서 다익스트라 연산을 3번 실행하여 각각의 최단거리를 구하고 2가지 케이스중 최소값을 답으로 출력하였다.

(3번만 실행해도 되는 이유는 b to c와 c to b에서 쓰는 값이 같기 때문이다. 코드에는 가독성을 위해 4번 연산했다.)

 

거리 배열을 만들 때 INF(1e7)로 초기화하여 정답이 INF(1e7)보다 크다면 갈 수 없다고 판단해 -1로 정답을 교체해 주었다.

 

전체적인 설명은 마루리하고 코드를 보며 설명하는 시간을 가지겠습니다. (필요 없을시 하단의 코드전문 참조)

---

우선, 다익스트라에 필요한 우선순위 최소 큐를 작성하기 편하게 typedef를 통해 priorityMinQue로 만들어 주었습니다.

typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> priorityMinQue;

 

전역 변수와 dijkstra 함수를 선언해 주었습니다. edgeArrays는 우선순위 최소 큐를 가지는 벡터입니다. (사실 그냥 배열로 해도 상관 없습니다.)

int nodeCnt, edgeCnt;
const int INF = 1e7;

vector<int> dijkstra(int curNode, vector<priorityMinQue> edgeArrays);

 

입력값을 받고 edgeArrays를 채워줍니다.

int main()
{
    cin >> nodeCnt >> edgeCnt;
    vector<priorityMinQue> edgeArrays(nodeCnt + 1);

    for (int i = 0; i < edgeCnt; i++)
    {
        int a, b, length;
        cin >> a >> b >> length;
        edgeArrays[a].push({b, length});
        edgeArrays[b].push({a, length});
    }

 

꼭 들러야 하는 지점을 받아 사진처럼 계산하기 위해서 다익스트라 함수를 호출해 줍니다. (다익스트라 내부는 설명 생략)

    int fst, sec;
    cin >> fst >> sec;
    vector<int> startToMin = dijkstra(1, edgeArrays);
    vector<int> fstToMin = dijkstra(fst, edgeArrays);
    vector<int> secToMin = dijkstra(sec, edgeArrays);
    vector<int> endToMin = dijkstra(nodeCnt, edgeArrays);

 

이후 answer의 2 Case 중 최소를 정하고 갈 수 없는 경로인지 확인 후 정답을 출력합니다.

    int answer = min(startToMin[fst] + fstToMin[sec] + endToMin[sec],
                     startToMin[sec] + secToMin[fst] + endToMin[fst]);

    if (answer >= INF)
    {
        answer = -1;
    }
    cout << answer;
}

 

◆코드 전문◆

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

using namespace std;

int nodeCnt, edgeCnt;
vector<int> minLen;
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>>
    edgeArrays;

vector<int> daic(int curNode, int curLen)
{
    minLen = vector<int>(nodeCnt + 1, 1e8);
    minLen[curNode] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>
        queArrays;
    vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>>
        edgeArraysB = edgeArrays;

    queArrays.push({0, 0});
    while (!queArrays.empty())
    {
        queArrays.pop();
        while (!edgeArraysB[curNode].empty())
        {
            int nextNode, nextLen;
            tie(nextNode, nextLen) = edgeArraysB[curNode].top();
            edgeArraysB[curNode].pop();
            if (curLen + nextLen < minLen[nextNode])
            {
                minLen[nextNode] = curLen + nextLen;
                queArrays.push({minLen[nextNode], nextNode});
            }
        }
        tie(curLen, curNode) = queArrays.top();
    }

    return minLen;
}

int main()
{

    cin >> nodeCnt >> edgeCnt;
    edgeArrays = vector<
        priority_queue<pair<int, int>,
                       vector<pair<int, int>>,
                       greater<>>>(nodeCnt + 1);
    minLen = vector<int>(nodeCnt + 1, 1e8);

    for (int i = 0; i < edgeCnt; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edgeArrays[a].push({b, c});
        edgeArrays[b].push({a, c});
    }

    int fst, sec;
    cin >> fst >> sec;
    vector<int> startToMin = daic(1, 0);
    vector<int> fstToMin = daic(fst, 0);
    vector<int> secToMin = daic(sec, 0);
    vector<int> endToMin = daic(nodeCnt, 0);

    int answer = min(startToMin[fst] + fstToMin[sec] + endToMin[sec],
                     startToMin[sec] + secToMin[fst] + endToMin[fst]);

    if (answer >= 1e8)
    {
        answer = -1;
    }
    cout << answer;
}