골드4 - 백준 1504 특정한 최단 경로

백준 1504 특정한 최단 경로

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

접근방법

이 문제는 반드시 지나야하는 정점이 2개 있다. 따라서 시작점에서 출발해 정점1, 2를 어떤 순서로 거쳐가는 것이 빠른지 구해주어야 했고, 정점 1, 2에서 다익스트라를 통해서 종료 지점까지의 최단 거리와 정점 1, 2 사이의 최단 거리를 구해주어 모든 조합 중 가장 최단 거리를 출력해주었다.

풀이

우선 시작점에서 다익스트라를 이용하여 정점 1, 2까지의 최단거리를 구하여 저장해주었다.
그리고 다시 정점 1에서 다익스트라를 이용하여 도착 지점까지의 거리와 2번 정점까지의 거리를 구해주었고, 정점 2에서 다시 다익스트라를 이용하여 도착 지점까지의 거리를 구해주었다.
앞서 구한 값들을 이용하여 시작점 -> 정점 1 -> 정점 2 -> 도착지점, 시작점 -> 정점 2 -> 정점 1 -> 도착지점의 경로로 이동하는 거리를 비교해주어 더 짧은 거리를 answer에 저장해 출력해주었다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

vector<pair<int, int>> route[801];
int visited[801];

void dijikstra(int start)
{
	memset(visited, -1, sizeof(visited));
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	visited[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		int cur = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
        
        if (visited[cur] < cost)
			continue;
		for (int i = 0; i < route[cur].size(); i++)
		{
			if (visited[route[cur][i].first] == -1 || visited[route[cur][i].first] > cost + route[cur][i].second)
			{
				visited[route[cur][i].first] = cost + route[cur][i].second;
				pq.push({ cost + route[cur][i].second, route[cur][i].first });
			}
		}
	}
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		route[a].push_back({ b,c });
		route[b].push_back({ a,c });
	}

	int t1, t2;
	cin >> t1 >> t2;

	dijikstra(1);
	int s_to_t1 = visited[t1];
	int s_to_t2 = visited[t2];

	dijikstra(t1);
	int t1_to_e = visited[N];
	int t1_to_t2 = visited[t2];

	dijikstra(t2);
	int t2_to_e = visited[N];

	int answer = min(s_to_t1 + t1_to_t2 + t2_to_e, s_to_t2 + t1_to_t2 + t1_to_e);

	if ((s_to_t1 == -1 || t1_to_t2 == -1 || t2_to_e == -1) && (s_to_t2 == -1 || t1_to_e == -1))
		answer = -1;
	
	cout << answer << endl;
	return 0;
}