[백준] 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;
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;
}