[C++] 백준 18352 - 특정 거리의 도시 찾기

다익스트라를 활용한 간단한 문제.

다익스트라를 사용하면서 거리가 k가 될때 정답 벡터에 넣어주면 된다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
#define pii pair<int, int>
using namespace std;

int n, m, k, x;
vector<pii> v[300001];
int dist[300001];
vector<int> ans;

void dijikstra(int start) {
	for (int i = 0; i <= n; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	priority_queue<pii, vector<pii>, greater<>> pq;
	pq.push({ 0, start });
	while (!pq.empty()) {
		int current = pq.top().second;
		int current_dist = pq.top().first;
		pq.pop();
		for (int i = 0; i < v[current].size(); i++) {
			int next = v[current][i].second;
			int next_dist = v[current][i].first;
			if (dist[next] > current_dist + next_dist) {
				dist[next] = current_dist + next_dist;
				pq.push({ dist[next], next });
				if (dist[next] == k) ans.push_back(next);
			}
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> k >> x;
	for (auto i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back({ 1, b });
	}

	dijikstra(x);

	sort(ans.begin(), ans.end());
	if (ans.size() == 0) {
		cout << -1 << endl;
	}
	else {
		for (auto& i : ans) {
			cout << i << endl;
		}
	}
	
	return 0;
}