[백준/c++] 31230번 - 모비스터디

[ 문제 ]

[ 구현 ]

다익스트라 알고리즘을 어떻게 활용할 것인지에 대해 먼저 설계하고 풀기 시작하는 것이 좋다.

 

다익스트라 알고리즘은 어떠한 한 점으로부터 다른 모든 점들까지의 최단거리를 구해주기 때문에

A->B의 경로 상에 있는 점인지 확인하려면

A,B 를 기준점으로 다익스트라 알고리즘을 각각 돌리고

그로부터 구해진 어떠한 한점 i까지의 최단거리를 더했을때 (dist_a[i] + dist_b[i])

이것이 a와 b사이의 최단거리 dist_a[b](dist_b[a])과 같은지 확인하면 된다.

 

주의사항은 간선간의 거리가 10^9이고 주어진 점들의 개수가 2*10^5이므로 

초기 INF값을 충분히 크게 해줘야 하며, 데이터를 담을 벡터 배열의 자료형을 long long으로 해줘야 한다.

 

 

[ 코드 ]

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define INF 2e16

typedef long long ll;

using namespace std;

int n, m, a, b;
vector<pair<int,ll>> v[200001];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
ll dist[200001];
ll dist2[200001];

void dijstra(int x) {
	fill(dist + 1, dist + n + 1, INF);
	dist[x] = 0;

	pq.push({ 0,x });

	while (!pq.empty()) {
		ll st_cur_dist = pq.top().first;
		int cur = pq.top().second;

		pq.pop();

		if (dist[cur] < st_cur_dist) continue;

		for (auto e : v[cur]) {
			int next = e.first;
			ll start_next_dist = e.second + st_cur_dist;

			if (dist[next] > start_next_dist) {
				dist[next] = start_next_dist;
				pq.push({ start_next_dist, next });
			}
		}
	}
}

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

	cin >> n >> m >> a >> b;

	int x, y, dis;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> dis;
		v[x].push_back({ y,dis });
		v[y].push_back({ x,dis });
	}

	dijstra(a);

	for (int i = 1; i <= n; i++) {
		dist2[i] = dist[i];
	}

	dijstra(b);

	vector<int> ans;

	for (int i = 1; i <= n; i++){
		if (dist2[i] + dist[i] == dist[a]) {//b->a로 가는 거리와 a->i + b->i가 같은지 확인
			ans.push_back(i);
		}
	}

	sort(ans.begin(), ans.end());

	cout << ans.size() << '\n';

	for (auto x : ans) {
		cout << x << " ";
	}

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

문제의 조건을 잘 읽지 않고 무작정 다익스트라 알고리즘을 적용해, long long이 아닌 int로 자료형을 설정하는 실수를 범했다. 한번 꼬이기 시작하면 실수가 잘 보이지 않기에 처음 문제를 풀때부터 조건을 하나하나 차분하게 따져보는 것이 중요할 듯하다.