[P4] 백준 22870번 산책 (large) C++ 다익스트라

리뷰

 

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

뭐가 문제일까 싶을때 간선 정렬을 가중치 우선이 아닌 노드 번호 우선을 해주니 AC를 받았다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• v : 노드 방문 여부를 저장할 배열
• Edge : 간선 정보를 정의할 구조체, 노드 번호가 같다면 가중치, 아니라면 노드 번호순으로 오름차순 정렬한다.
• edges : 간선 정보를 인접 리스트로 저장하기 위한 Edge타입 벡터 배열
• Pos : 현재 노드와 누적 가중치 정보를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

vector<int> dijkstra(int sn) {
	priority_queue<Pos> pq;
	pq.push({ sn, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[sn] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

			if (!v[nn] && dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv });
			}
		}
	}
	return dist;
}

 

시작 노드에서 모든 노드까지의 최단 거리를 구하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 인접 리스트 edges를 초기화 시켜준다.
2. 1~n번 노드를 순회하며 sort함수를 통해 자신의 인접 리스트를 정렬해준다.
3. 변수 sn, dn에 시작 노드와 도착 노드의 번호를 입력 받아준다.
4. 벡터 dist1에 dijkstra함수를 통해 dn에서 갈 수 있는 모든 노드까지의 최단 경로를 구해준다.
5. 변수 cost를 0, cur를 sn으로 초기화 하고, cur이 dn에 도달할 때 까지 while루프를 수행해 준다.
6. 매 루프마다 cur의 인접 리스트를 순회하며 cost + dist1[nn] + nv가 dist1[sn]인 케이스를 찾는다.
7. 해당 케이스를 찾았다면 cost에 nv를 더해주고, cur을 nn, v[cur]에 방문처리 후 break처리해 준다.
8. while루프가 종료되었을 경우 v[dn]을 false처리하여 목적지의 방문을 해제해 준다.
9. 벡터 dist2에 dijkstra함수를 통해 sn에서 갈 수 있는 모든 노드까지의 최단 경로를 구해준다.
10. cost와 dist2[dn]을 더한 값을 출력해 준다.

 

트러블 슈팅

1. 인접 리스트를 정렬할 때 가중치 우선, 같다면 노드 번호 우선으로 오름차순 정렬해 주었다가 Fail을 받았다.
2. 인접 리스트를 노드 번호를 기준으로 오름차순으로 정렬해 주니 AC를 받았다.

 

참고 사항

1. 노드는 최대 20만개, 간선의 가중치는 최대 1000이므로 int범위 내로 처리할 수 있다.
2. 정점의 번호는 1부터 시작한다, 산책을 할 수 있는 경로가 있는 데이터만 주어진다.
3. 정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다. 따라서 노드 번호로만 정렬해 주면 된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 2e5 + 1;
int n, m;
bool v[N];
struct Edge {
	int nn, nv;
	bool operator<(const Edge& other) const {
		return nn < other.nn;
	}
};
vector<Edge> edges[N];
struct Pos {
	int cn, cv;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

vector<int> dijkstra(int sn) {
	priority_queue<Pos> pq;
	pq.push({ sn, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[sn] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

			if (!v[nn] && dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv });
			}
		}
	}
	return dist;
}

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

	cin >> n >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	for (int i = 1; i <= n; ++i) sort(edges[i].begin(), edges[i].end());

	int sn, dn; cin >> sn >> dn;

	vector<int> dist1 = dijkstra(dn);
	int cost = 0, cur = sn;
	while (cur != dn) {
		for (const Edge& edge : edges[cur]) {
			int nn = edge.nn, nv = edge.nv;

			if (cost + dist1[nn] + nv == dist1[sn]) {
				cost += nv;
				cur = nn;
				v[cur] = true;
				break;
			}
		}
	}

	//for (int i = 1; i <= n; ++i) cout << v[i] << " ";
	//cout << "\n";

	v[dn] = false;
	vector<int> dist2 = dijkstra(sn);
	cout << cost + dist2[dn];
}