백준 1738번 : 골목길 - 벨만 포드 알고리즘 C++

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

1738번: 골목길

1. 문제설명

 

간선의 cost를 뺏기는 양으로 두면

금을 땅에서 주울 경우에는 마이너스

뺏길 경우는 플러스로 두게 되어 이동하는데 필요한 cost를 설정할 수 있다.

이후 벨만포드 알고리즘을 적용해서 풀면 된다.

 

단 이 문제의 경우 음의 사이클이 존재한다고 무조건 -1이 될 수 없다.

왜냐하면 음의 사이클이 존재해도 시작점에서 도착점까지 가는데 경유하지 않을 수 있기 때문이다

즉 음의사이클이 존재는 하나 따로 동떨어진 경우가 테스트케이스로 들어올 수도 있다.

 

그래서 음의사이클이 존재하고 음의사이클에서 도착점으로 가는지 판단해야한다.

또한 출발점 1에서 도착점 n까지 도달할 수 있는지 확인해야한다.

 

이를 위해 역방향 간선을 저장해두고 n으로부터 시작하여 BFS를 돌면

1과 음의 사이클에서 도착점까지 갈 수 있는지 확인할 수 있다.

 

 

---

 

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const long long INF = 1e18;
long long dist[101];
int pre[101];

int n, m;
vector<pi> adj[101];
vector<pi> rev_adj[101];

bool goal[101];

void check_goal() {
	queue<int> Q;

	Q.push(n);
	goal[n] = 1;

	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (auto &i : rev_adj[x]) {
			int nx = i.first;
			if (goal[nx] == 0) {
				Q.push(nx);
				goal[nx] = 1;
			}
		}
	}
}

void print(int n) {

	if (n == 0) return;
	print(pre[n]);
	cout << n << ' ';
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,-w });
		rev_adj[v].push_back({ u,-w });
	}
	
	check_goal();

	//시작점에서 도착점 가는 길이 없는 경우
	if (goal[1] == 0) {
		cout << -1 << '\n';
		return 0;
	}

	fill(dist, dist + 101, INF);

	dist[1] = 0;



	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {

			for (auto& a : adj[j]) {
				int nx = a.first;
				int d = a.second;

				if (dist[j] != INF && dist[nx] > dist[j] + d) {
					pre[nx] = j;
					dist[nx] = dist[j] + d;

					if ((i == n-1) && (goal[j])) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
	}


	print(n);


	return 0;
}

백준 1738번 골목길