[백준] 14496 그대, 그머가 되어

0

백준

목록 보기
258/271
post-thumbnail

[백준] 14496 그대, 그머가 되어

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

int N, M;
vector<vector<int>> adj(1001, vector<int>());

int solve(int start, int dest) {
	int res = -1;

	//<curMove, curNum>
	priority_queue<pair<int, int>> q;
	q.push({ 0, start });

	int visited[1001] = { 0 };

	while (!q.empty()) {
		int curMove = -q.top().first;
		int curNum = q.top().second;
		q.pop();

		if (visited[curNum]) continue;
		visited[curNum] = 1;

		if (curNum == dest) {
			res = curMove;
			break;
		}

		for (int i = 0; i < adj[curNum].size(); ++i) {
			int nextNum = adj[curNum][i];
			if (visited[nextNum]) continue;

			q.push({ -(curMove + 1), nextNum });
		}
	}

	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int a, b;
	cin >> a >> b;
	cin >> N >> M;

	for (int i = 0; i < M; ++i) {
		int first, second;
		cin >> first >> second;

		adj[first - 1].push_back(second - 1);
		adj[second - 1].push_back(first - 1);
	}

	cout << solve(a - 1, b - 1);

	return 0;
}

profile
Be able to be vulnerable, in search of truth

0개의 댓글