백준 1504 - 특정한 최단 경로

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

1504번: 특정한 최단 경로

문제 설명

---

방향성이 없는 그래프가 주어질때, 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다.

또한, 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로 구한다.

그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것.

한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라.

1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

 

접근 방식

---

문제 접근 방식은 최단거리를 떠올리게 되고 Dijkstra에서 조건을 추가하는 방식으로 문제를 해결하였다.

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
const int INF =987654321;
using namespace std;
int n,m;    
int sp,ep;
vector<pair<int,int> >v[200001];
vector<int>dijkstra(int start, int num){
    vector<int>weight(num,INF);
    priority_queue<pair<int,int> >pq;
    weight[start]=0;
    pq.push(make_pair(0,start));
    while(!pq.empty()){
        int cost = pq.top().first;
        int vert = pq.top().second;
        pq.pop();
        for(int i=0;i<v[vert].size();i++){
            int neighbor= v[vert][i].first;
            int neighbordistance = v[vert][i].second+cost;
            if(neighbordistance < weight[neighbor]){
                weight[neighbor]=neighbordistance;
                pq.push(make_pair(-neighbordistance,neighbor));
            }
        }
    }
    return weight;
}
int main(){
   cin>>n>>m;    
   n++;
   for(int i=0;i<m;i++){
       int start,end,cost;
       cin>>start>>end>>cost;
       //양방향성
       v[start].push_back(make_pair(end,cost));
       v[end].push_back(make_pair(start,cost));
   }
   cin>>sp>>ep;
   vector<int> result = dijkstra(1, n);
   vector<int> temp1 = dijkstra(sp, n);
   vector<int> temp2 = dijkstra(ep, n);
	//1. 1 -> startpoint -> endpoint -> N
    //2. 1 -> endpoint -> startpoint -> N
   int answer = min((result[sp] + temp1[ep] + temp2[n - 1]), (result[ep] + temp2[sp] + temp1[n - 1]));
   if (answer >= INF || answer < 0) cout << -1 << "\n";
   else cout << answer << "\n";
   return 0;
}

 

 

funny algorithms :0 ~