[BOJ]백준 1219번: 오민식의 고민(C++)/Bellman-Ford

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

1219번: 오민식의 고민

조금 어려웠던 벨만포드 문제 ~~~~

아주 전형적인 벨만포드 문제라면 음수 사이클의 존재 여부만 체크할텐데

 

이 문제에서는 음수 사이클이 존재하는지 & 해당 사이클에서 목적 노드로의 path가 있는지 또한 검사해야 했다

그래서 3번이 처음에는 음수 사이클이 존재한다면 Gee를 출력하는 줄 알았지만 ~~

여러개의 음수 사이클이 존재하더라도, 하나의 음수 사이클에서라도 도착지로 가는 path가 있을 경우에 Gee를 출력하도록 변경해주었다

 

보통 그래프를 인접행렬/인접리스트/간선배열 형태로 입력받게 되고 대부분은 앞의 두 경우인데 이 문제에서는 간선배열 형태로 입력받았다

노드의 개수 및 간선 개수가 많지 않았기 때문에 dfs도 문제없이 동작했다

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF -987654321
using namespace std;

typedef struct { int u, v, w; }edge;
vector<edge> e;
int n, m, graph[105][105], city[105], pre[105], s, f;
long long dist[105];
bool visit[105];

bool dfs(int cur) {
	if (cur == f)return true;
	visit[cur] = true;
	bool chk = false;
	for (auto x : e) {
		if (x.u == cur && !visit[x.v])
			chk |= dfs(x.v);
	}
	return chk;
}

int main() {
	scanf("%d%d%d%d", &n, &s, &f, &m);
	fill(&dist[0], &dist[n + 1], INF);

	for (int i = 0, u, v, w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		e.push_back({ u,v,w });
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &city[i]);
	}

	dist[s] = city[s];
	pre[s] = -1;
	for (int k = 0; k < n-1; k++)
		for (auto x : e) {
			if (dist[x.u] != INF && (dist[x.v] < dist[x.u] - x.w + city[x.v]))
				dist[x.v] = dist[x.u] - x.w + city[x.v];
		}

	if (dist[f] == INF)printf("gg");
	else {

		for (auto x : e) {
			if (dist[x.u] != INF && (dist[x.v] < dist[x.u] - x.w + city[x.v]))
				if (dfs(x.u)) {
					printf("Gee");
					return 0;
				}
		}
		printf("%lld", dist[f]);
	}
	return 0;
}