특정한 최단 경로(1504, G4, c++)

특정한 최단 경로

특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 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에서 N으로 가는 최단 경로를 구하는데 v1,v2라는 점을 반드시 지나야 한다.
이 때 착각하기 쉬운 것이 1 - v1 - 1 - v2 - N과 같은 경로가 더 짧을 경우를 생각하는 것이다.

다익스트라의 특성상 v1을 start를 잡으면 어떤 점을 거쳐서라도 v2까지 가는 최소 경로를 찾는다.
그러므로 v1-1-v2같은 경로가 가장 짧다면 v1-v2를 구할 때 알아서 구해진다는 것이다.

그렇기에 v1, v2를 지나는 경로를 구할 때 고려할 것은 1-v1-v2-N과 1-v2-v1-N 밖에 없다.
이렇게 기준을 잡아 다익스트라 3번을 통해서 쉽게 구할 수 있었다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int a, b, c, d;
    int n, m, t;
    char ch;
    
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n+1);
    for(int i=0;i<m;i++){
      cin >> a >> b >> c;
      graph[a].push_back({b,c});
      graph[b].push_back({a,c});
    }
    cin >> a >> b;
    priority_queue<pair<int, int>> pq;
    vector<int> dist_s(n+1, 1e8);
    pq.push({0, 1});
    dist_s[1]=0;
    while(!pq.empty()){
      int node = pq.top().second;
      int di = -pq.top().first;
      pq.pop();
      for(int i=0;i<graph[node].size();i++){
        if(dist_s[graph[node][i].first]>di+graph[node][i].second){
          dist_s[graph[node][i].first] = di+graph[node][i].second;
          pq.push({-dist_s[graph[node][i].first], graph[node][i].first});
        }
      }
    }
    vector<int> dist_v1(n+1, 1e8);
    pq.push({0, a});
    dist_v1[a]=0;
    while(!pq.empty()){
      int node = pq.top().second;
      int di = -pq.top().first;
      pq.pop();
      for(int i=0;i<graph[node].size();i++){
        if(dist_v1[graph[node][i].first]>di+graph[node][i].second){
          dist_v1[graph[node][i].first] = di+graph[node][i].second;
          pq.push({-dist_v1[graph[node][i].first], graph[node][i].first});
        }
      }
    }
    vector<int> dist_v2(n+1, 1e8);
    pq.push({0, b});
    dist_v2[b]=0;
    while(!pq.empty()){
      int node = pq.top().second;
      int di = -pq.top().first;
      pq.pop();
      for(int i=0;i<graph[node].size();i++){
        if(dist_v2[graph[node][i].first]>di+graph[node][i].second){
          dist_v2[graph[node][i].first] = di+graph[node][i].second;
          pq.push({-dist_v2[graph[node][i].first], graph[node][i].first});
        }
      }
    }

    int ans = min(dist_s[a]+dist_v1[b]+dist_v2[n], dist_s[b]+dist_v1[n]+dist_v2[a]);
    if(ans>=1e8)cout << "-1";
    else cout << ans;
    return 0;
}