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;
}