[백준 1504] 특정한 최단 경로 (C++)

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

1504번: 특정한 최단 경로

문제

---

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

---

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

문제 풀이

---

그래프 문제에서 1번 정점에서 N번 정점까지의 최단 경로의 길이를 구하는 문제이므로 다익스트라 알고리즘을 사용하는 문제이다.

단 N번 정점까지 가는데 임의의 두 정점을 통과해야 한다. 이때 N번까지 가는 경우의 수가 2가지 있다.

1번 정점 - 임의의 정점 A - 임의의 정점 B - N번정점 순으로 가는 경우와

1번 정점 - 임의의 정점 B - 임의의 정점 A - N번 정점 순으로 가는 경우이다.

첫번째 경우와 두번째 경우 각각 한 정점부터 다음 정점까지의 최단 경로를 구해 세 개의 최단 경로 길이를 모두 더해준다. 그리고 첫번째 경우와 두번째 경우 중 어떤 것이 짧은 최단 경로인지 비교해 출력해주면 된다.

경로 중 첫번째 경우와 두번째 경우 모두 어떤 정점- 다음 정점의 최단 경로를 구할 때 갈 수 있는 길이 없어 N번까지 도달하지 못할 때에는 문제 제시대로 -1을 출력한다. 

 

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
int* distanceArr;
int N;
vector<pair<int, int>>* v;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int startNode)
{
	distanceArr[startNode] = 0;
	pq.push(make_pair(0, startNode));
	while (!pq.empty())
	{
		pair<int, int> current = pq.top();
		int cost = current.first;
		int currentNode = current.second;
		
		pq.pop();
		if (cost > distanceArr[currentNode])
		{
			continue;
		}
		else
		{
			for (int i = 0; i < v[currentNode].size(); i++)
			{
				pair<int, int> next = v[currentNode].at(i);
				int nextNode = next.first;
				int dist = next.second;
				if (cost + dist < distanceArr[nextNode])
				{
					distanceArr[nextNode] = cost + dist;
					pq.push(make_pair(cost + dist, nextNode));
				}
			}
		}
	}
}

void resetDistanceArr()
{
	for (int i = 0; i < N + 1; i++)
	{
		distanceArr[i] = 987654321;
	}
}

int getMinCost(int first, int second)
{
	int cost;
	dijkstra(1);
	if (distanceArr[first] == 987654321)
	{
		return -1;
	}
	cost = distanceArr[first];
	resetDistanceArr();
	dijkstra(first);
	if (distanceArr[N] == 987654321)
	{
		return -1;
	}
	cost += distanceArr[second];
	resetDistanceArr();
	dijkstra(second);
	if (distanceArr[N] == 987654321)
	{
		return -1;
	}
	cost += distanceArr[N];
	return cost;
}

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

	int E;
	int start, end, cost;
	int vertex1, vertex2;
	cin >> N>>E;
	v=new vector<pair<int, int>>[N+1];
	distanceArr = new int[N + 1];
	resetDistanceArr();
	for (int i = 0; i < E; i++)
	{
		cin >> start >> end >> cost;
		v[start].push_back(make_pair(end, cost));
		v[end].push_back(make_pair(start, cost));
	}
	cin >> vertex1 >> vertex2;
	int firstRouteCost = getMinCost(vertex1, vertex2);
	resetDistanceArr();
	int secondRouteCost = getMinCost(vertex2, vertex1);
	if (firstRouteCost == -1 && secondRouteCost == -1)
	{
		cout << -1 << "\n";
	}
	else
	{
		cout << min(firstRouteCost, secondRouteCost) << "\n";
	}
	return 0;
}