백준 소스코드 [C++] 13913 숨바꼭질 4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

백준 소스코드 [C++] 13913 숨바꼭질 4

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
typedef long long ll;
using namespace std;
int V, E, W, v, e;
int path[100001];
void dijkstra(int src) {
	priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	pair<int, int> p;
	vector<int> trace;
	q.push({ 0,src });
	memset(path, -1, sizeof(path));
	while (q.empty() != true) {
		p = q.top();
		if (p.second == e) break;
		q.pop();
		if (p.second * 2 <= 100000 && path[p.second * 2] == -1) {
			q.push({ p.first + 1,p.second * 2 });
			path[p.second * 2] = p.second;
		}
		if (p.second + 1 <= 100000 && path[p.second + 1] == -1) {
			q.push({ p.first + 1,p.second + 1 });
			path[p.second + 1] = p.second;
		}
		if (0 <= p.second - 1 && path[p.second - 1] == -1) {
			q.push({ p.first + 1,p.second - 1 });
			path[p.second - 1] = p.second;
		}
	}
	cout << p.first << '\n';

	while (e != v) {
		trace.push_back(e);
		e = path[e];
	}
	trace.push_back(v);
	for (int i = (int)trace.size() - 1;0 <= i;i--)cout << trace[i] << " ";
	return;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> v >> e;
	dijkstra(v);
	return 0;
}