(1504) 특정한 최단 경로

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

단계별로 풀어보기

29단계(최단 경로) 2번째

 

 

 

v1과 v2를 경유하여 1번 정점에서 N번 정점으로 가는 경우는 두 가지이다.

1 → v1 → v2 → N

1 → v2 → v1 → N

따라서 1, v1, v2번 정점 각각을 시작점으로 하여 다익스트라 알고리즘을 세 번 돌린 뒤 더 작은 값을 출력하면 된다.

 

주의사항으로 정점이 최대 800개, 간선 가중치가 최대 1000이므로 최단거리의 최댓값은 약 80만이다. 하지만 정답은 경로 3개의 합이기 때문에 이론상 가능한 정답의 최댓값은 약 240만이다. INF값을 타이트하게 잡았다면 틀린다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
#define INF 2400000
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, e, v1, v2;
  
  cin >> n >> e;
  
  priority_queue<p, vector<p>, greater<p>> pq;
  vector adj(n+1, vector<p>());
  vector<int> dist(n+1, INF);
  
  while(e--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj[a].push_back({c, b});
    adj[b].push_back({c, a});
  }
  
  cin >> v1 >> v2;
  
  auto dijk= [&](int start){
    dist= vector<int> (n+1, INF);
    
    dist[start]= 0;
    pq.push({0, start});
    
    while(!pq.empty()){
      p now= pq.top();
      pq.pop();
      
      if(now.first>dist[now.second])  continue;
      
      for(p next:adj[now.second]){
        if(now.first+next.first<dist[next.second]){
          dist[next.second]= now.first+next.first;
          pq.push({now.first+next.first, next.second});
        }
      }
    }
  };
  
  dijk(1);
  int one_v1= dist[v1], one_v2= dist[v2];
  dijk(v1);
  int v1_v2= dist[v2], v1_n= dist[n];
  dijk(v2);
  int v2_v1= dist[v1], v2_n= dist[n];
  
  int ans= min(one_v1+v1_v2+v2_n, one_v2+v2_v1+v1_n);
  
  cout << (ans>=INF ? -1 : ans);
  
  return 0;
}