1504: 특정 최단 경로(BOJ C/C++)

1504호:확실한 최단 경로

사용 언어: C++

설명

//1번 정점에서 시작, n번 정점으로 이동.
//시작 정점이 주어지고 최단경로이므로 다익스트라 알고리즘을 활용하면 된다.
//주어진 두 정점을 반드시 거쳐야한다. 만약 a, b 정점을 거쳐야한다면 
// 1 -> a -> b -> n or 1 -> b -> a -> n 두 가지 경우만 구하면 된다.
// 그러면 a와 b 각각에서 다익스트라를 돌리면 모든 값을 구할 수 있다. -> 다익스트라 두 번만 돌리면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9
using namespace std;

int n, e; //n: 정점 개수, e: 간선 개수
int v1, v2; //거쳐야하는 정점 v1, v2

vector<pair<int,int>> arr(801);
int dist(2)(801); //dist(0) -> a에서 돌린 값, dist(1) -> b에서 돌린 값.

void dijkstra(int num, int start)
{
	priority_queue<pair<int, int>> pq; //<<거리, 인덱스>>
	pq.push({0, start});
	dist(num)(start) = 0;
	
	while(!pq.empty())
	{
		int dist2 = -pq.top().first; //현재 노드까지의 거리
		int cur = pq.top().second; //현재 노드
		pq.pop();
		
		for(int i=0; i<arr(cur).size(); i++)
		{
			int next = arr(cur)(i).first;
			int cost = dist2 + arr(cur)(i).second;
			
			if(cost < dist(num)(next))
			{
				dist(num)(next) = cost;
				pq.push({-cost, next});
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> e;
	
	for(int i=0; i<e; i++)
	{
		int a, b, c; //a번 정점에서 b 정점까지 거리가 c
		cin >> a >> b >> c;
		arr(a).push_back({b,c});
		arr(b).push_back({a,c}); //양방향이므로
	}
	
	fill(&dist(0)(0), &dist(2)(0) + 1, INF);
	
	cin >> v1 >> v2;
	dijkstra(0, v1); //v1에서 모든 정점 거리
	dijkstra(1, v2); //v2에서 모든 정점 거리
	
	int sum1, sum2 = 0;
	
	//INF인 경우가 없어야 아래 sum1, sum2 비교 성립
    if (dist(0)(1) == INF || dist(0)(v2) == INF || dist(1)(n) == INF)
        sum1 = INF;
    else
        sum1 = dist(0)(1) + dist(0)(v2) + dist(1)(n); //1~v1 + v1~v2 + v2~n

    if (dist(1)(1) == INF || dist(1)(v1) == INF || dist(0)(n) == INF)
        sum2 = INF;
    else
        sum2 = dist(1)(1) + dist(1)(v1) + dist(0)(n); //1~v2 + v2~v1 + v1~n

	if(min(sum1,sum2) >= INF)
		cout << -1 << '\n';
	else
		cout << min(sum1, sum2) << '\n';
	
	return 0;
}