[class4] (백준 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) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v₁과 v₂가 주어진다. (v₁ ≠ v₂, v₁ ≠ N, v₂ ≠ 1)

출력

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

제한

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

힌트

 

 

#include <iostream>
#include <vector>
#include <queue>
#define MAXNUM 801
#define INF 987654321
using namespace std;
struct Info
{
	int goal;
	int value;
};
int arr[MAXNUM][MAXNUM];
int dp[MAXNUM];

vector<Info> v[MAXNUM];

int N, E;

void ResetDP(int start)
{
	queue<int> q;

	for (int i = 1; i <= N; i++)
	{
		dp[i] = INF;
	}
	dp[start] = 0;
	q.push(start);

	while (!q.empty())
	{
		int currentNum = q.front();
		q.pop();
		vector<Info> current = v[currentNum];

		for (auto iter = current.begin(); iter < current.end(); iter++)
		{
			if (dp[iter->goal] > dp[currentNum] + iter->value)
			{
				dp[iter->goal] = dp[currentNum] + iter->value;
				q.push(iter->goal);
			}
		}
	}
}

int Solve(int wayPoint1,int wayPoint2)
{
	int value1 = 0,value2 = 0;
	ResetDP(1);
	value1 += dp[wayPoint1];
	value2 += dp[wayPoint2];

	ResetDP(wayPoint1);
	if (value1 != INF) value1 += dp[wayPoint2];
	if (value2 != INF) value2 += dp[N];

	ResetDP(wayPoint2);
	if (value1 != INF) value1 += dp[N];
	if (value2 != INF) value2 += dp[wayPoint1];

	if (value1 >= INF && value2 >= INF)
	{
		return -1;
	}
	return value1 < value2 ? value1 : value2;
}

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

	cin >> N >> E;

	int n1, n2, val;
	for (int i = 0; i < E; i++)
	{
		cin >> n1 >> n2 >> val;
		v[n1].push_back({ n2,val });
		v[n2].push_back({ n1,val });
	}

	int wayPoint1, wayPoint2;
	cin >> wayPoint1 >> wayPoint2;
	cout << Solve(wayPoint1, wayPoint2);

	return 0;
}