[백준/BOJ] 백준 1504번 : 특정한 최단 경로

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

1504번: 특정한 최단 경로

다익스트라 알고리즘을 이용하여 어떤 정점에서 다른 정점으로 가는 최단 경로를 구하였다. 주어진 정점(2개)을 거쳐서 0번 정점(1번 정점)부터 n-1번 정점(n번 정점)으로 가는 최단 경로는 0 -> v1-1 -> v2-1 -> n-1 (1->v1->v2->n)과 0 -> v2-1 -> v1-1 -> n-1 (1->v2->v1->n) 이 두 가지 경우중 작은 것이다

 

코드

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int n, e;
int a, b, c;
vector<pair<int, int>> adj[800];
int v1, v2;

//start정점에서 각 정점으로 가는 최단경로를 구하는 다익스트라 알고리즘
vector<int> Solve(int start)
{
	vector<int> result(n, 200000001);

	priority_queue<pair<int, int>> pq;

	result[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (result[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (result[there] > there_cost)
			{
				result[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}

	return result;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int result;
	int result_temp1;
	int result_temp2;
	int start_v1, v1_v2, v2_dest;
	int start_v2, v2_v1, v1_dest;
	vector<int> short_path;

	//정점의 번호가 0부터 시작하는 그래프로 풀었습니다
	cin >> n >> e;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		adj[a-1].push_back(make_pair(c, b-1));
		adj[b-1].push_back(make_pair(c, a-1));
	}
	cin >> v1 >> v2;

	short_path = Solve(0);
	start_v1 = short_path[v1 - 1];
	start_v2 = short_path[v2 - 1];

	short_path = Solve(v1 - 1);
	v1_v2 = v2_v1 = short_path[v2 - 1];
	v1_dest = short_path[n - 1];

	short_path = Solve(v2 - 1);
	v2_dest = short_path[n - 1];

	//무조건 주어진 정점을 거쳐서 0번 정점(1번 정점)부터 n-1번 정점(n번 정점)으로 가는 최단 경로는 이 두가지 경우중 작은 것이다
	result_temp1 = start_v1 + v1_v2 + v2_dest; //0 -> v1-1 -> v2-1 -> n-1 (1->v1->v2->n)
	result_temp2 = start_v2 + v2_v1 + v1_dest; //0 -> v2-1 -> v1-1 -> n-1 (1->v2->v1->n)

	result = min(result_temp1, result_temp2);

	if (result >= 200000001)
		cout << -1;
	else
		cout << result;

	return 0;
}