[백준 1219 | C++] 오만식의 고민::벨만-포드

• 문제 링크 : 1219번: 오민식의 고민
• 문제 태그 : 그래프 이론,그래프 탐색,  최단 경로,벨만-포드
• 참고 자료 : 2025.01.22 - [BOJ] - [백준 11657 | C++] 타임머신::벨만-포드

[백준 11657 | C++] 타임머신::벨만-포드

 

풀이

두 가지 항목을 통해 경우의 수를 4가지로 나누었습니다.

• 음수 사이클이 존재하는가?
• 도착 도시에 도달할 수 있는가?

이를 통해서 Gee, gg, 액수의 최댓값을 출력하는 경우를 나누었습니다.
 
이때 고려하지 못한 하나의 경우가 잇었으니.... 
사실은 음수 사이클이 존재하는 경우를 2개의 상황으로 더 세분화 했어야합니다. 반례는 주의사항에 써두었습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const long long INF = 1LL << 60;
bool dfs(int n, int s, int e, vector<vector<int>>& g);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, s, e, m;
	cin >> n >> s >> e >> m;
	vector<vector<int>> v(m, vector<int>(3, 0));
	vector<vector<int>> g(n);
	vector<int> money(n, 0);
	for (int i = 0;i < m;i++) {
		cin >> v[i][0] >> v[i][1] >> v[i][2];
		g[v[i][0]].push_back(v[i][1]);
	}

	for (int i = 0;i < n;i++) {
		cin >> money[i];
	}

	for (int i = 0;i < m;i++) {
		int f = v[i][0];	// from
		int t = v[i][1];	// to
		int c = v[i][2];	// cost

		c -= money[t];
		v[i][2] = c;
	}

	vector<long long>dist(n, INF);
	dist[s] = -money[s];

	if (!dfs(n, s, e, g)) {
		cout <<  "gg";
		return 0;
	}
	
	for (int i = 0;i < n - 1;i++) {
		for (int j = 0;j < m;j++) {
			int f = v[j][0];	
			int t = v[j][1];	
			int c = v[j][2];
			
			if (dist[f] != INF && dist[t] > dist[f] + c) {
				dist[t] = dist[f] + c;
			}
		}
	}

	// 음수 사이클 검사
	bool flag = false;
	for (int j = 0;j < m;j++) {
		int f = v[j][0];
		int t = v[j][1];
		int c = v[j][2];

		if (dist[f] != INF && dist[t] > dist[f] + c) {
			if (dfs(n, f, e, g)) {
				flag = true;
			}
		}
	}

	if (flag) cout << "Gee";
	else {
		cout << -dist[e];
	}
}

bool dfs(int n, int s, int e, vector<vector<int>> &g) {
	vector<int>seen(n, false);
	stack<int>stk;
	stk.push(s);
	seen[s] = true;
	
	while (!stk.empty()) {
		int t = stk.top();
		stk.pop();
		for (auto x : g[t]) {
			if (!seen[x]) {
				seen[x] = true;
				stk.push(x);
			}
		}
	}

	if (seen[e]) return true;
	else return false;
 }

 

주의사항 (반례)

5 0 4 5
0 4 1
4 2 1
1 2 -1
3 1 -1
2 3 -1
0 0 0 0 0

 
음수 사이클이 최단 경로에 포함되지 않는 경우이다. 
이 경우 음수 사이클이 확인된 정점에서 도착 도시로 갈 수 있는지 dfs를 통해 검사하였습니다.

---

ICPC Sinchon 25W 에서 최단 경로를 다뤄서 벨만-포드 문제를 풀어보았습니다. 주의사항에 써 둔 반례를 찾지 못했는데 중급 강사님(jinhan814)님이 도움을 주셨습니다👍