[BOJ 32936 // C++] 타임머신

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 32936번 문제인 타임머신이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/32936

 

답이 "-inf"가 되려면 일단 (1) 1번 정점에서 타임머신을 이용하러 갈 수 있으며 (2) 타임머신 이용 후 다시 타임머신을 이용하러 갈 수 있고 (3) 2의 과정에 드는 시간이 타임머신으로 되돌아가는 시간보다 적으며 (4) 타임머신 이용 후 \(N\)번 정점으로 이동할 수 있어야 한다.

 

위의 내용이 성립하지 않으면 일단 답은 "-inf'가 아니다. 이 때 가능한 답의 후보는 (1)1번 정점에서 타임머신을 이용하지 않고 \(N\)번 정점으로 가는 것과 (2) 1번 정점에서 타임머신을 한 번 이용하고 \(N\)번 정점으로 가는 것이다. 타임머신을 2번 이상 사용하는 것이 1번 사용한 것보다 더 거리가 짧다면 타임머신을 더 많이 사용하는 것이 이득이 됨을 관찰하자.

 

아래는 제출한 소스코드이다.

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

int N, M, A, B, C;
vector<int> G[200001];
queue<int> que;
int dist[200001];
int dd = 1000000007, da = 1000000007, db = 1000000007, dba = 1000000007;

void bfs(int S) {
	memset(dist, 0, sizeof(dist));
	dist[S] = 1;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto &nxt:G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> A >> B >> C;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	bfs(1);
	if (dist[N]) dd = dist[N] - 1;
	if (dist[A]) da = dist[A] - 1;
	bfs(B);
	if (dist[N]) db = dist[N] - 1;
	if (dist[A]) dba = dist[A] - 1;

	if (da < 1000000007 && db < 1000000007) dd = min(dd, da + db - C);
	if (da < 1000000007 && db < 1000000007 && dba < 1000000007 && dba < C) cout << "-inf";
	else if (dd < 1000000007) cout << dd;
	else cout << 'x';
}