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

다익스트라를 복습하기 위해서 문제를 풀어보았다.

 

 

사실 이렇게 해서 풀릴 줄 몰랐는데

그냥 다익스트라를 여러 번 돌려서 해결되었다.

 

정점 2개를 무조건 지나가야 하기 때문에

시작 지점, 정점1, 정점2에서 다익스트라를 이용해 한 번씩 돌려 거리 값을 구하고

최소 거리를 계산하는 방식으로 해결했다.

#include <iostream>
#include <string.h>
#include <vector>

#include <queue>

using namespace std;

int INF = 98765432;
long NodeDist[801];
vector<pair<int, int>> Nodes[801];
int N, E;

void BFS(int start)
{
	memset(NodeDist, INF, sizeof(NodeDist));
	NodeDist[start] = 0;

	queue<int> q;
	q.push(start);
	
	while (!q.empty())
	{
		int from = q.front();
		q.pop();

		for (int i = 0; i < Nodes[from].size(); ++i)
		{
			int to = Nodes[from][i].first;
			int length = Nodes[from][i].second + NodeDist[from];

			if (NodeDist[from] > NodeDist[to])
				continue;

			if (NodeDist[to] > length )
			{
				q.push(to);
				NodeDist[to] = length;
			}

		}

	}


}

// 데익스트라
int main()
{
	cin >> N >> E;
	int a, b, c, v1, v2;

	for (int i = 0; i < E; ++i)
	{
		// from 'a' to 'b' = c
		cin >> a >> b >> c;
		Nodes[a].push_back({b, c});
		Nodes[b].push_back({a, c});

	}

	int answer = 0;
	cin >> v1 >> v2;
	
	// BFS
	BFS(1);
	int from1_to_v1Dist = NodeDist[v1];
	int from1_to_v2Dist = NodeDist[v2];

	BFS(v1);
	int fromv1_to_v2Dist = NodeDist[v2];
	int fromv1_to_endDist = NodeDist[N];

	BFS(v2);
	int fromv2_to_v1Dist = NodeDist[v1];
	int fromv2_to_endDist = NodeDist[N];

	int t1 = (from1_to_v1Dist + fromv1_to_v2Dist + fromv2_to_endDist);
	int t2 = (from1_to_v2Dist + fromv2_to_v1Dist + fromv1_to_endDist);

	answer = min(t1, t2);

	if (answer >= INF)
	{
		cout << "-1";
		return 0;
	}

	cout << answer;
}