[BOJ 5590 // C++] 船旅

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5590번 문제인 船旅이다.
문제는 아래 링크를 확인하자.

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

5590번: 船旅

100 이하의 정수 N개의 섬과 이들 사이의 선박편의 비용이 주어지는 그래프가 주어진다.

 

0번 쿼리가 주어지면 주어지는 두 섬 사이의 최단거리를 출력하고, 1번 쿼리가 주어지면 새로운 배편을 그래프에 추가하자.

 

섬의 개수 N과 쿼리의 수 K가 적으므로, 어떤 그래프 최단거리 알고리즘을 사용해도 문제를 해결할 수 있다.

 

그 중 두 섬 사이의 최단거리가 갱신되었을 때 O(N)의 추가연산만으로 모든 섬 사이의 최단거리를 갱신할 수 있는 Floyd-Warshall 알고리즘이 가장 효율이 좋을 것으로 예상된다.

 

글쓴이는 최단거리를 구할 때마다 Dijkstra 알고리즘을 돌려 문제를 해결하였다.

 

아래는 제출한 소스코드이다.

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

int N, Q;
vector<pair<int, int>> G[101]; // (좌표, 거리)
int dist[101];

int dijkstra(int s, int e) {
	memset(dist, 0, sizeof(dist));
	dist[s] = 1;
	priority_queue<pair<int, int>> pq; // (-거리, 좌표)
	pq.push(make_pair(-1, s));
	while (!pq.empty()) {
		int cur = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (dist[cur] < d) continue;
		for (auto p : G[cur]) {
			int node = p.first, dd = p.second;
			if (dist[node] == 0 || d + dd < dist[node]) {
				dist[node] = d + dd;
				pq.push(make_pair(-(d + dd), node));
			}
		}
	}

	return dist[e] - 1;
}

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

	cin >> N >> Q;
	while (Q--) {
		int q; cin >> q;
		if (q == 0) {
			int x, y; cin >> x >> y;
			cout << dijkstra(x, y) << '\n';
		}
		else {
			int x, y, d; cin >> x >> y >> d;
			G[x].emplace_back(make_pair(y,d));
			G[y].emplace_back(make_pair(x,d));
		}
	}
}