백준 1504 특정한 최단 경로 (c++)

 

일반적인 다익스트라 알고리즘을 사용하여

반드시 들러야 하는 두 정점이 있다는것을 생각해야 한다.

주의할 점은 두 정점을 들르는 순서는 관계없다는 점

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <climits>

#define ll long long
using namespace std;

int n, e;
vector < vector<pair<int, int>>> arr;
int v[3] = { 0, };

vector<int> dijkstra(int start)
{
	vector<int> visit(n+1, INT_MAX);
	visit[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		int current = pq.top().second;
		int dist = -pq.top().first;
		pq.pop();
		for (auto a : arr[current])
		{
			int nxt = a.first;
			int ndist = dist + a.second;
			if (ndist < visit[nxt])
			{
				visit[nxt] = ndist;
				pq.push({ -ndist, nxt });
			}
		}
	}
	return visit;
}

정석적인 우선순위 큐를 이용한 다익스트라 알고리즘이다

다익스트라를 여러번 돌려야 함으로 시작점을 받아올 수 있는 함수 형태로 빼줬다

 

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n >> e;
	arr.resize(n+1);
	for (int i = 0; i < e; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
		arr[b].push_back({ a,c });
	}
	v[0] = 1;
	for (int i = 1; i <= 2; i++)
	{
		cin >> v[i];
	}

양방향 통행이 자유로운 간선이므로 반대방향도 같이 넣어준다

들러야 하는 정점은 편의상 v배열에 시작노드인 1, v1 v2을 같이 넣어줬다

 

vector<int> visit1 = dijkstra(v[0]);
int startTov1 = visit1[v[1]]; //1->v1
int startTov2 = visit1[v[2]]; //1->v2

vector<int> visit2 = dijkstra(v[1]);
vector<int> visit3 = dijkstra(v[2]);

int v1Tov2 = visit2[v[2]];
int v1Toend = visit2[n];
int v2Tov1 = visit3[v[1]];
int v2Toend = visit3[n];

 

들러야 하는 정점에 순서가 없으므로 모든 경우의 수를 다 구해줘야 한다

다익스트라 알고리즘을 매번 돌릴 필요가 없도록 다익스트라 함수에선 완성된 최단 배열 거리 배열을 반환하도록 했다

 

모든 경우의 수를 구하려면

시작노드1 -> v1 ->v2 ->도착노드 n

시작노드1 -> v2 ->v1 ->도착노드 n

경로 내의 최단 거리를 전부 저장해주고 비교해야 한다

 

int p1 = -1, p2 = -1;
if(startTov1 != INT_MAX && v1Tov2 != INT_MAX && v2Toend != INT_MAX)
	p1 = startTov1 + v1Tov2 + v2Toend;
if (startTov2 != INT_MAX && v2Tov1 != INT_MAX && v1Toend != INT_MAX)
	p2 = startTov2 + v2Tov1 + v1Toend;

중간 과정중 하나라도 갱신안된 값이 있으면 길이 끊겨있으므로 해당 경우는 성립 하지 않는다

 

if (p1 == -1 && p2 == -1)
{
	cout << -1 << endl;
	return 0;
}
else if (p1 == -1)
{
	cout << p2 << endl;
	return 0;
}
else if (p2 == -1)
{
	cout << p1 << endl;
	return 0;
}

두 경우 모두 끊겨 있으면 답은 없으므로 -1을 출력

둘중 하나만 막혀있으면 다른쪽이 정답

 

if (p1 > p2)
{
	cout << p2 << endl;
}
else
{
	cout << p1 << endl;
}
return 0;

둘 다 문제 없으면 둘중 최단거리를 정답으로 출력한다