백준 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) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.

출력

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

 

 

 

 

아이디어는 우선적으로 루트를 나눠서 각각 다익스트라로 돌려서 다른 출력값을 만드는 것이 핵심.

 

 

 

 

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


using namespace std;


int N, M;

const int INF = 987654321;
vector<pair<int, int> > vec[801];




int dijkstra(int start, int end) 
{ 
       int distance[N+1]; 
       
       
for(int k=1; k<=N; k++) 
{ 

distance[k] = INF; 

} 

      
     
     priority_queue<pair<int, int> > pr; 

     pr.push({start,0}); 
      distance[start] = 0; 



while(!pr.empty()) 
{ 


int current = pr.top().first; 
int cost = pr.top().second; 


pr.pop(); 

if(distance[current] < cost) //이거 없어도 최단경로가 아니면 업데이트 안되므로 결과는 같음 but 시간차이발생.

continue; 








    for(int i = 0; i<vec[current].size(); i++) 
    { 
     int next = vec[current][i].first; 
     
     int nextcost = cost + vec[current][i].second; 
     
     
     
     if(distance[next] > nextcost) 
     { 
     
     
     pr.push({next,nextcost}); 
     
     distance[next] = nextcost; 
} 
} 


} 



return distance[end]; 


} 

int main(void)
{

cin >> N >> M;


for(int i =0 ; i<M; i++)
{
int a,b,c;

cin >> a >> b >> c;

vec[a].push_back({b,c});
vec[b].push_back({a,c});



}

int tos1,  tos2 ;

cin >> tos1 >> tos2;


int A = dijkstra(1,tos1) + dijkstra(tos1,tos2) + dijkstra(tos2,N);
int B = dijkstra(1,tos2) + dijkstra(tos2,tos1) + dijkstra(tos1,N);

    int C= min(A,B);
    
    if(C>=INF || C<0)
    {
     cout << -1 <<endl;
}else{

 cout << C <<endl;
}
   



}