[BOJ/C++] 1504 특정한 최단 경로

https://www.acmicpc.net/problem/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) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

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

예제 입력 1
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
예제 출력 1
7

문제 정리

이 문제는 다익스트라로 해결할 수 있다. 조건이 하나가 붙는데, 입력받은 2개의 정점을 반드시 지나야 하는 것이다. 또 헷갈릴 수 있는 부분이 있는데 정점의 개수 N개이고 그 중 우리는 1번부터 N번 정점까지의 거리만 구하면 된다. 반드시 지나야 하는 두 정점을 v1, v2라고 하자. 1번 부터 N번 정점까지 가는 경로는

i) 1 -> v1 -> v2 -> N
ii) 1->-> v2 -> v1 -> N

이렇게 두가지 경우가 나온다.
1 -> v1 -> v2 -> N 이 경로를 구하는 방법은

1-> v1 까지의 최단거리를 다익스트라로 구한다.
v1-> v2 까지의 최단거리를 다익스트라로 구한다.
v2-> N 까지의 최단거리를 다익스트라로 구한 뒤 다 더한다.

1->-> v2 -> v1 -> N 경로도 이와같은 방법으로 구할 수 있다.

i) 1 -> v1 -> v2 -> N
ii) 1->-> v2 -> v1 -> N
두 경로 중 거리가 더 짧은 경우의 거리가 출력값이다.

코드

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;


vector <pair<int,int>> adj[802];
int dist[802];
const int INF = 1e9;

int n,m;
int a,b,cost;

//다익스트라 알고리즘
long long dijkstra(int st, int en)
{
    priority_queue <pair<int,int>, vector<pair<int,int>>, 
                         greater<pair<int,int>> > pq;
    fill(dist,dist+n+1,INF);
    dist[st] = 0;
    pq.push({0,st});
    while(!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        if(dist[cur.Y]!=cur.X)
            continue;
        for(auto nxt : adj[cur.Y])
        {
            if(dist[nxt.Y] <= dist[cur.Y] + nxt.X)
                continue;
            dist[nxt.Y] = dist[cur.Y] + nxt.X;
            pq.push({dist[nxt.Y], nxt.Y});
        }
    }
    return dist[en];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    
  
    for(int i=0; i<m; i++)
    {
        cin >> a >> b >> cost;
        adj[a].push_back({cost,b});
        adj[b].push_back({cost,a});
    }

    int x,y;
    cin >> x >> y;

    long long res = INF;
   
    long long case1,case2;
    case1 = dijkstra(1,x) + dijkstra(x,y) + dijkstra(y,n);
    case2 = dijkstra(1,y) + dijkstra(y,x) + dijkstra(x,n);
    if(case1 <= case2)
        {res = min(res,case1);}
    else
        {res = min(res,case2);}

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