[백준 1738] 골목길 (C++)

문제 링크: https://www.acmicpc.net/problem/1738

1738번: 골목길

1. 주의할 점

- 양의 사이클이 아닌, 가중치를 전부 -1로 곱하여 음의 사이클을 구하도록 한다

- 경로를 어떤 방식으로 저장할 것인가

- 사이클이 있다고 무조건 -1을 출력하는 것이 아니다 -> 도착지점까지 이동중, 음의 사이클이 존재한다면 -1 출력

 

2. 구현

- 음의 사이클이 존재하므로 벨만포드 알고리즘을 사용한다

- Bellman_ford() 함수를 수행하면서, Previous[]에 해당 Node에 도착하기 전까지 최단 거리의 Node번호를 기록한다

- 음의 사이클이 경로상에 존재하지 않는다면, Previous를 통해 이전 Node로 계속 움직이며 1이 나올 때까지 Ans 벡터에 값을 넣는다

 

#define MAX 987654321
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int idx;
	long long val;
};
info tmp;
int node, edge, s, e, val;
vector<info> v[101];
vector<int> rev[101];		//Node번호에서 역으로 추적하여 닿을 수 있는 Node들 check
long long dist[101];
bool cycle = false;
int previous[101];
bool visit[101] = { false, };

void bellman_ford() {
	for (int k = 1; k <= node; k++) {
		for (int i = 1; i <= node; i++) {
			int from = i;
			for (int j = 0; j < v[from].size(); j++) {
				int to = v[from][j].idx;
				int nv = v[from][j].val;
				if (dist[from]!=MAX && dist[to] > dist[from] + nv) {
					dist[to] = dist[from] + nv;
					previous[to] = from;
					if (k == node && visit[to])
						cycle = true;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		val *= -1;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
		rev[e].push_back(s);
	}
	queue<int> q;
	q.push(node);
	visit[node] = true;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < rev[cidx].size(); i++) {
			int next = rev[cidx][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
			}
		}
	}
	for (int i = 2; i <= node; i++)
		dist[i] = MAX;
	bellman_ford();
	if (cycle)
		cout << -1;
	else {
		vector<int> ans;
		int idx = node;
		while (1) {
			ans.push_back(idx);
			if (idx == 1)	break;
			else	idx = previous[idx];
		}
		for (int i = ans.size() - 1; i >= 0; i--)
			cout << ans[i] << " ";
	}
	system("pause");
	return 0;
}