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

1504 특정한 최단 경로

문제

---

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

---

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

---

풀이)

다익스트라를 이용한 문제이다.

1부터 두 개의 정점 v1, v2를 무조건 지나고 N까지 가는 경로를 찾으면 되니깐 아래와 같이 2개의 경로를 찾으면 된다.

경로1 : 1 → v1 → v2 → N

경로2 : 1 → v2 → v1 → N

3번의 다익스트라를 진행해 각 경로에 해당하는 값을 더한다.

① 1 부터 v1와 v2의 거리를 구하는 다익스트라 => (1→v1) (1→v2)

② v1 부터 v2와 N의 거리를 구하는 다익스트라 => (v1→v2) (v1→N)

③ v2 부터 v1와 N의 거리를 구하는 다익스트라 => (v2→v1) (v2→N)

모든 계산 후 경로1과 경로2 중 작은 값을 출력하면 된다.

(만일 작은 경로의 값이 경로가 없을 때 나오는 값 즉, INF 면 -1 출력)

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 555555555 //절대나올수없는값
int n;//정점의 개수
vector <pair<int, int>>adj[801];
 
vector <int> Dijkstra(int start) {
    vector <int> dist(n + 1, INF);
    priority_queue <pair<int, int>> qu;
    dist[start] = 0; //자기자신은 0
    qu.push({ 0,start });
    while (!qu.empty())
    {
        int load = -qu.top().first;
        int here = qu.top().second;
        qu.pop();
        if (dist[here] < load) continue;
        for (int i = 0; i < adj[here].size(); i++) {
            int next = adj[here][i].first;
            int nextdist = adj[here][i].second + dist[here];
 
            if (dist[next] > nextdist) {
                dist[next] = nextdist;
                qu.push({ -nextdist,next });
            }
 
        }
    }
    return dist;
}
 
int main() {
    int m;//r간선개수
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int start, end, load;
        scanf("%d %d %d", &start, &end, &load);
        //무방향
        adj[start].push_back({ end,load });
        adj[end].push_back({ start,load });
    }
    int vec1, vec2;//거쳐야하는 정점들
    long long minidist1 = 0, minidist2 = 0;//출발지에서 vec1을 먼저갈경우, vec2를 먼저갈경우
    scanf("%d %d", &vec1, &vec2);
 
    //1 ->vec1, vec1->vec2, vec2->N 총 3번진행
    //1 ->vec2, vec2->vec1, vec1->N
    vector <int> check = Dijkstra(1);
    minidist1 += check[vec1];
    minidist2 += check[vec2];
 
    check = Dijkstra(vec1);
    minidist1 += check[vec2];
    minidist2 += check[n];
 
    check = Dijkstra(vec2);
    minidist1 += check[n];
    minidist2 += check[vec1];
 
    if (minidist1 < minidist2) {
        if (minidist1 >= INF) {
            printf("-1");
        }
        else {
            printf("%lld", minidist1);
        }
    }
    else {
        if (minidist2 >= INF) {
            printf("-1");
        }
        else {
            printf("%lld", minidist2);
        }
 
    }
    return 0;
 
}