백준 1504 - 특정한 최단 경로

문제링크

• 백준 1504

문제설명

• 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
• 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

문제접근

• 다익스트라 알고리즘 을 v1, v2 를 시작지점으로 모든 정점에 도달하는 최소 비용을 계산한다.
• 1번 정점에서 출발하여 v1, v2 를 거쳐 N번 정점에 도달하는 경우의 수는 다음과 같다.
  1. 1 -> v1 -> v2 -> N
  2. 1 -> v2 -> v1 -> N
  3. 1 -> v1 -> v2 -> v1 -> N
  4. 1 -> v2 -> v1 -> v2 -> N
• v1 -> N, v2 -> N 비용에 따라 이미 방문했던 v1 혹은 v2 를 재방문한 후 N번 정점에 도달하는 것이 최소비용이 되는 경우가 있다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#define MAX_E 200000
#define MAX_N 800

using namespace std;
int N, E;
int v1, v2;
int costInfo[2][3]; // costInfo[0] 은 v1에서 1, v2, N 으로 갈 때 필요한 최소비용을 의미
int cand[4];
bool bOne_V1 = true, bV1_V2 = true, bV2_N = true, bOne_V2 = true, bV1_N = true;
vector<pair<int, int>> graph[MAX_E];

void Dijkstra(int start)
{
	int sIdx;
	if (start == 0) sIdx = v1;
	if (start == 1) sIdx = v2;

	vector<int> dist(N + 1, INT_MAX);
	dist[sIdx] = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(0, sIdx));

	while (!q.empty())
	{
		int u = q.front().second;
		int cost = q.front().first;
		q.pop();
		
		if (dist[u] < cost) continue;

		for (int i = 0; i < graph[u].size(); i++)
		{
			int v = graph[u][i].second;
			int x = graph[u][i].first;

			if (cost + x < dist[v])
			{
				dist[v] = cost + x;
				q.push(make_pair(cost + x, v));
			}
		}
	}
	
	costInfo[start][0] = dist[1];
	costInfo[start][2] = dist[N];
	if (sIdx == v1) costInfo[start][1] = dist[v2];
	else if (sIdx == v2) costInfo[start][1] = dist[v1];

	// update status
	if (start == 0)
	{
		if (costInfo[start][0] == INT_MAX) bOne_V1 = false;
		if (costInfo[start][1] == INT_MAX) bV1_V2 = false;
		if (costInfo[start][2] == INT_MAX) bV1_N = false;
	}
	else if (start == 1)
	{
		if (costInfo[start][0] == INT_MAX) bOne_V2 = false;
		if (costInfo[start][2] == INT_MAX) bV2_N = false;
	}
}

void UpdateCandCost()
{
	
	if (bOne_V1 && bV1_V2 && bV2_N)
	{
		// 1 -> v1 -> v2 -> N
		cand[0] = costInfo[0][0] + costInfo[0][1] + costInfo[1][2];
		
		// 1 -> v1 -> v2 -> v1 -> N
		cand[1] = costInfo[0][0] + 2 * costInfo[0][1] + costInfo[0][2];
	}
	else
	{
		cand[0] = INT_MAX;
		cand[1] = INT_MAX;
	}

	
	if (bOne_V2 && bV1_V2 && bV1_N)
	{
		// 1 -> v2 -> v1 -> N
		cand[2] = costInfo[1][0] + costInfo[1][1] + costInfo[0][2];

		// 1 -> v2 -> v1 -> v2 -> N
		cand[3] = costInfo[1][0] + 2 * costInfo[1][1] + costInfo[1][2];
	}
	else
	{
		cand[2] = INT_MAX;
		cand[3] = INT_MAX;
	}
}

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

	cin >> N >> E;
	for (int i = 0; i < E; i++)
	{
		int from, to, weight;
		cin >> from >> to >> weight;
		graph[from].push_back(make_pair(weight, to));
		graph[to].push_back(make_pair(weight, from));
	}
	cin >> v1 >> v2;
	
	Dijkstra(0); // v1
	Dijkstra(1); // v2
	UpdateCandCost();

	int ans = INT_MAX;
	for (int i = 0; i < 4; i++)
	{
		if (cand[i] == INT_MAX) continue;
		ans = min(cand[i], ans);
	}
	if (ans == INT_MAX) cout << "-1\n";
	else cout << ans << endl;
}