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

문제

방향성이 없는 간선이 주어지고 정점 1부터 정점 N까지 도착하는 최단 경로를 구하는 것이다. 이때 정점 X, Y를 경유하는 최단 경로를 구해야 하는 문제이다.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 <= N <= 800, 0 <= E <= 200,000)

 

둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 A, B, C가 주어지는데, A번 정점에서 B번 정점까지 양방향 길이 존재하며, 그 거리가 C라는 것이다.

 

마지막 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 X, Y가 주어진다.

 

예제 입력

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

예제 출력

7

문제 해결

어디서 힌트를 얻을 수 있을까?

 

이 문제를 읽을 때 정점, 간선, 가중치, 그리고 최단 거리라는 키워드를 보고 이 문제는 다익스트라 알고리즘을 사용해서 풀면 간단하게 풀 수 있다고 생각했다.

 

우선 반드시 지나야 하는 정점 X, Y가 존재하기 때문에 가능한 경우의 수는 다음과 같다.

• S → X → Y → N
• S → Y → X → N

즉, S, X,그리고 Y로 시작하는 최단 거리 배열을 구하면 위의 값을 비교한 후 더 짧은 것이 정답이 된다.

 

여기에서 주의해야 할 점은 INF를 여러번 더할 수 있기 때문에 자료형을 long long으로 하는 것을 유의하자.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

struct Node {
	int idx;
	long long dis;
};

struct cmp {
	bool operator()(std::pair<int, long long> a, std::pair<int, long long> b)
	{
		if (a.second > b.second)
			return true;
		else if (a.second == b.second)
		{
			if (a.first > b.first)
				return true;
			else
				return false;
		}
		return false;
	}
};

long long INF = 999999999;
std::vector<Node> varr[801];
long long disArr[3][801];

void Daijkstra(int flag, int Node)
{
	std::priority_queue<std::pair<int, long long>, std::vector<std::pair<int, long long> >, cmp> pqarr;
	pqarr.push(std::make_pair(Node, 0));
	disArr[flag][Node] = 0;
	int curNode;
	long long curDis;
	while (!pqarr.empty())
	{
		curNode = pqarr.top().first;
		curDis = pqarr.top().second;
		pqarr.pop();
		if (curDis > disArr[flag][curNode])
			continue;
		for (int i = 0; i < varr[curNode].size(); i++)
		{
			int nNode = varr[curNode][i].idx;
			long long nDis = curDis + varr[curNode][i].dis;
			if (disArr[flag][nNode] > nDis)
			{
				disArr[flag][nNode] = nDis;
				pqarr.push(std::make_pair(nNode, nDis));
			}
		}
	}
}

void init(void)
{
	for (int i = 0; i < 801; i++)
	{
		disArr[0][i] = INF;
		disArr[1][i] = INF;
		disArr[2][i] = INF;
	}
}

int main(void)
{
	int N, M;
	std::cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int S, D, T;
		std::cin >> S >> D >> T;
		varr[S].push_back({D, T});
		varr[D].push_back({S, T});
	}
	init();
	int X, Y;
	std::cin >> X >> Y;
	Daijkstra(0, 1);
	Daijkstra(1, X);
	Daijkstra(2, Y);
	long long ret = std::min(disArr[0][X] + disArr[1][Y] + disArr[2][N],
				disArr[0][Y] + disArr[2][X] + disArr[1][N]);
	if (ret >= INF)
		std::cout << -1 << std::endl;
	else
		std::cout << ret << std::endl;
	return 0;
}

문제 출처

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

1504번: 특정한 최단 경로

이론

https://deulee.tistory.com/10

다익스트라(Dijkstra) 알고리즘