18352번: 특정 거리의 도시 찾기

Memo

로직 설명

• priority_queue를 이용하여 min_heap을 구현합니다. 거리를 음수 처리하여 넣고, 뺄때는 다시 마이너스 처리를 해서 원래 값으로 복원합니다.
• 거리 정보가 들어있는 값 보다 (현재 누적받은 거리 + 1)이 더 작으면 업데이트를 해주고 priority_queue에 넣어줍니다.

Code

제출 날짜

2021/05/10

메모리

24448 KB

시간

448 ms

#include <iostream>
#include <vector>
#include <queue>
#define endl "\\n"
#define INF 3000000

int distance[300001];
std::vector<int> graph[300001];
std::priority_queue<std::pair<int, int> > pq;
int N, M, K, X;

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int node1, node2;

	io_faster();
	std::cin >> N >> M >> K >> X;
	for (int i = 0 ; i < M ; i++)
	{
		std::cin >> node1 >> node2;
		graph[node1].push_back(node2);
	}
	for (int i = 1 ; i <= N ; i++)
		distance[i] = INF;
}

void solve()
{
	int current, d, c_size, next, next_cost, fl = 0;

	distance[X] = 0;
	pq.push({0, X});
	while(!pq.empty())
	{
		d = -pq.top().first;
		current = pq.top().second;
		pq.pop();
		c_size = graph[current].size();
		if (d > distance[current])
			continue;
		for (int i = 0 ; i < c_size ; i++)
		{
			next = graph[current][i];
			next_cost = d + 1;
			if (next_cost > distance[next])
				continue;
			distance[next] = next_cost;
			pq.push({-next_cost, next});
		}
	}

	for (int i = 1 ; i <= N ; i++)
	{
		if (distance[i] == K)
		{
			std::cout << i << endl;
			fl = 1;
		}
	}
	if (!fl)
		std::cout << -1;
}

int main()
{
	input();
	solve();
	return (0);
}