[G4] 백준 12834번 주간 미팅 C++ 다익스트라

리뷰

 

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

다익스트라 알고리즘을 통해 최단 거리를 구하는 문제

 

 

전역 변수

• n : KIST 기사단 팀원의 수를 저장할 변수
• v : 노드의 개수를 저장할 변수
• e : 간선의 개수를 저장할 변수
• a, b : KIST와 씨알푸드 노드 번호를 저장할 변수
• Edge : 간선의 이동할 노드 node, 가중치 val을 정의할 구조체
• edges : 간선 정보를 인접리스트로 저장할 Edge타입 벡터 배열
• lst : KIST 기사단의 노드 번호를 저장할 배열
• ans : 정답을 저장할 변수
• Pos : 이동 정보의 현재 노드 node, 누적 가중치 val을 정의할 구조체, val을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra(int sn)

 

시작 노드로 부터 KIST, 씨알 푸드까지 걸리는 최단 거리의 합을 구하는 함수

1. 매개 변수로 시작 노드의 번호 sn을 입력 받아준다.
2. Pos타입의 우선순위 큐 pq를 초기화 하고, 시작 노드와 누적 가중치 0을 push해준다.
3. v + 1크기의 벡터 dist를 초깃값을 매우 큰 값으로 초기화 해준다.
4. 시작 노드의 dist값을 0으로 저장해 준다.
5. pq가 빌 때 까지 while 루프를 수행해 주고, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 인접 리스트를 순회하며 이동할 노드의 dist값이 누적 가중치와 간선의 가중치를 더한 값보다 크다면 갱신해 준다.
7. while 루프가 종료된 후 만약 dist의 a, b인덱스의 값이 초깃값과 동일하다면 -1로 변경해 준다.
8. dist[a], dist[b]를 더한 값을 리턴해 준다.

 

문제풀이

1. n, v, e, a, b에 각각 값을 입력 받아 저장해 준다.
2. n개의 KIST 기사단의 집 노드 번호를 lst배열에 입력 받아준다.
3. e개의 간선 정보를 입력 받아 양방향으로 edges배열에 추가해 준다.
4. n개의 KIST 기사단의 집 노드 번호를 각각 dijkstra함수의 매개변수로 전달하고 리턴값을 ans에 더해준다.
5. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 이동할 수 없는 목적지인 경우 -1로 변경해 준다.
• 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9
• 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2

 

정답 코드

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

int n, v, e, a, b;
struct Edge {
	int node, val;
};
vector<Edge> edges[1001];
int lst[100];
int ans;
struct Pos {
	int node, val;
	bool operator<(const Pos& other) const {
		return val > other.val;
	}
};

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

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

		for (const Edge& edge : edges[cn]) {
			int nn = edge.node, nv = edge.val;
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, cv + nv });
			}
		}
	}
	if (dist[a] == 2e9) dist[a] = -1;
	if (dist[b] == 2e9) dist[b] = -1;
	return dist[a] + dist[b];
}

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

	cin >> n >> v >> e >> a >> b;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	while (e--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	for (int i = 0; i < n; ++i) {
		ans += dijkstra(lst[i]);
	}

	cout << ans;
}