[G3] 백준 23801번 두 단계 최단 경로 2 C++ 다익스트라, 다이나믹 프로그래밍, unordered_set

리뷰

 

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

X부터 Z까지 이동하며 P개의 서로 다른 중간 정점을 방문했는지 여부의 상태를 체크하며 최단 거리를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• p : 중간에 들러야할 서로 다른 중간 노드의 개수를 저장할 변수
• x, z : 시작 노드와 도착 노드의 번호를 저장할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 인접 리스트를 저장할 Edge타입 벡터 배열
• dic : 중간에 들러야할 노드의 번호를 저장할 해시셋
• Pos : 현재 노드의 번호와 누적 시간, 유효한 정점을 지나왔는지를 정의할 구조체, 누적 시간을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

ll dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ x, 0, false });
	vector<vector<ll>> dist(n + 1, vector<ll>(2, 1e18));
	dist[x][0] = 0;

	while (!pq.empty()) {
		auto [cn, ct, cf] = pq.top(); pq.pop();

		if (dist[cn][cf] < ct) continue;
		if (cn == z && cf == true) return dist[cn][cf];

		for (const Edge& edge : edges[cn]) {
			auto [nn, w] = edge;

			ll nt = ct + w;
			bool nf = dic.count(nn) ? true : cf;
			if (dist[nn][nf] > nt) {
				dist[nn][nf] = nt;
				pq.push({ nn, nt, nf });
			}
		}
	}

	return -1;
}

 

X부터 Z까지 유효한 정점을 거쳐 도달하는 최단 거리를 구하는 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 edges를 초기화한다.
2. x, z, p값을 입력 받고, p개의 유효 정점의 번호를 입력 받아 dic을 초기화한다.
3. dijkstra함수를 호출한다.
4. Pos타입의 우선순위 큐 pq를 초기화하고, 초기값 {x, 0, false}를 push한다.
5. n+1*2크기의 정수형 벡터 dist의 초기값을 매우 큰 값으로 초기화한다.
6. dist[x][0]을 0으로 저장하여 시작점을 초기화한다.
7. pq가 빌때까지 while루프를 수행하고, 매 루프마다 pq에서 요소를 빼내어 변수 cn, ct, cf에 파싱한다.
8. 첫 번째 기저 조건으로 dist[cn][cf]가 ct보다 작은 경우 더 좋은 케이스가 있는 경우이므로 continue처리한다.
9. 두 번째 기저 조건으로 cn이 z이고, cf가 true인 경우 dist[cn][cf]를 리턴한다.
10. edges[cn]을 순회하며, 변수 nt에 이동 후 시간을 저장한다.
11. 변수 nf는 현재 노드가 dic에 포함되어 있다면 true, 아니라면 cf로 초기화한다.
12. dist[nn][nf]가 nt보다 클 경우 dist[nn][nf]를 nt로 저장하고, pq에 {nn, nt, nf}를 push한다.
13. while루프가 종료될때까지 기저 조건에 도달하지 못한 경우 -1을 리턴한다.
14. dijkstra함수의 리턴값을 출력한다.

 

트러블 슈팅

1. Pos, dist, dijkstra의 반환값을 int타입으로 설정하여 WA를 받았다.
2. 거리 관련 정수형을 long long타입으로 변경하여 AC를 받았다.

 

참고 사항

1. 노드의 개수는 최대 10만개, 간선의 가중치는 최대 100만이므로 int범위를 넘어설 수 있다.
2. dist는 유효 정점을 거쳤는지 여부를 체크하기 위해 상태를 관리해주었다.
3. 중간 정점 Y는 (1 ≤ Y ≤ N, X ≠ Y ≠ Z)조건을 가진다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<unordered_set>
using namespace std;
using ll = long long;

const int N = 1e5 + 1;
int n, m, p, x, z;
struct Edge {
	int nn, w;
};
vector<Edge> edges[N];
unordered_set<int> dic;
struct Pos {
	int cn;
	ll ct;
	bool flag;
	bool operator<(const Pos& other) const {
		return ct > other.ct;
	}
};

ll dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ x, 0, false });
	vector<vector<ll>> dist(n + 1, vector<ll>(2, 1e18));
	dist[x][0] = 0;

	while (!pq.empty()) {
		auto [cn, ct, cf] = pq.top(); pq.pop();

		if (dist[cn][cf] < ct) continue;
		if (cn == z && cf == true) return dist[cn][cf];

		for (const Edge& edge : edges[cn]) {
			auto [nn, w] = edge;

			ll nt = ct + w;
			bool nf = dic.count(nn) ? true : cf;
			if (dist[nn][nf] > nt) {
				dist[nn][nf] = nt;
				pq.push({ nn, nt, nf });
			}
		}
	}

	return -1;
}

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

	cin >> n >> m;
	while (m--) {
		int f, t, w; cin >> f >> t >> w;
		edges[f].push_back({ t, w });
		edges[t].push_back({ f, w });
	}

	cin >> x >> z >> p;
	while (p--) {
		int y; cin >> y;
		dic.insert(y);
	}

	cout << dijkstra();
}