백준 1504번 특정한 최단 경로 C++ 다익스트라, 최단 경로

리뷰

1부터 N까지의 최단 경로의 길이를 찾되, 반드시 두 정점을 거친 후 이동 해야하는 문제

 

문제 풀이

1. 노드의 개수 n과 간선의 개수 e를 입력 받고 인접리스트를 나타낼 2차 pair형 벡터 lst를 n + 1크기로 초기화 한다.
2. e개의 간선의 정보를 lst에 양방향 간선으로 추가해 주고, v1와 v2 값을 입력 받아준다.
3. 1 => v1 => v2 => N과 1 => v2 => v1 => N의 최단 경로를 각각 구해준다.
4. 두 경로 중 더 작은 값을 정답으로 출력하면 된다, 만약 두 경로 모두 INT_MAX라면 -1을 출력해 준다.

 

참고 사항

우선순위 큐의 자료형을 pair를 쓸 경우 greater<pair<int, int>>를 통해 쉽게 최소힙으로 변환할 수 있다.

INT_MAX를 사용해 주기 위해서는 climits를 include를 해줘야 한다. 안하면 나처럼 컴파일 에러가 난다...

 

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<climits>

using namespace std;

int n, e, v1, v2;
vector<vector<pair<int, int>>> lst;

int dijkstra(int sn, int dn) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, sn });
	vector<int> dist(n + 1, INT_MAX);
	dist[sn] = 0;

	while (!pq.empty()) {
		pair<int, int> cur = pq.top(); pq.pop();
		int cd = cur.first, cn = cur.second;
		if (dist[cn] != cd) continue;
		for (pair<int, int> next : lst[cn]) {
			int nd = next.first, nn = next.second;
			if (dist[nn] > cd + nd) {
				dist[nn] = cd + nd;
				pq.push({ dist[nn], nn });
			}
		}
	}
	return dist[dn];
}

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

	cin >> n >> e;
	lst.resize(n + 1);
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		lst[a].push_back({ c, b });
		lst[b].push_back({ c, a });
	}
	cin >> v1 >> v2;
	int d1 = dijkstra(1, v1);
	int d2 = dijkstra(v1, v2);
	int d3 = dijkstra(v2, n);

	int d4 = dijkstra(1, v2);
	int d5 = dijkstra(v2, v1);
	int d6 = dijkstra(v1, n);

	int ans1 = INT_MAX, ans2 = INT_MAX;
	if (d1 != INT_MAX && d2 != INT_MAX && d3 != INT_MAX) ans1 = d1 + d2 + d3;
	if (d4 != INT_MAX && d5 != INT_MAX && d6 != INT_MAX) ans2 = d4 + d5 + d6;
	int result = min(ans1, ans2);
	if (result != INT_MAX) cout << result;
	else cout << -1;
}