[BOJ 7040 // C++] 밥 먹기

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

 

이번에 볼 문제는 백준 7040번 문제인 밥 먹기이다.
문제는 아래 링크를 확인하자.

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

7040번: 밥 먹기

1번 소부터 i번 소까지의 거리를 Di라고 하자.

문제의 모든 조건을 Di를 이용하여 나타내보면 다음과 같다:

 

1) 두 소 사이의 거리는 0 이상이다: D(i+1) - Di >= 0

2) 두 소 사이의 거리는 1000000007 이하이다: D(i+1) - Di <= 1000000007

3) ML조건: 두 소 a와 b(a<b)사이 거리는 d 이하이다: Db - Da <= d

4) MD조건: 두 소 a와 b(a<b) 사이 거리는 d 이상이다: Db - Da >= d

 

이는 LP문제로, 각 식을 Di - Dj <= W의 꼴로 나타낼 수 있으므로 Bellman-Ford 알고리즘으로 풀 수 있는 케이스이다.

Bellman-Ford 알고리즘을 이용하여 위 system을 풀어내자. 이 때 Bellman-Ford 알고리즘은 DN 또한 최대화시켜주므로 문제를 해결할 수 있다.

 

음의 사이클이 발생한다면 -1을, DN이 10억을 넘어간다면 -2를, 그렇지 않다면 DN을 출력해주자.

 

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

#define INF 1000000000000000000LL
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct edge {
	int x, y;
	ll d;
	edge(int x, int y, ll d) {
		this->x = x, this->y = y, this->d = d;
	}
};

ll dist[1001];
vector<edge> edges;

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

	int N, ML, MD; cin >> N >> ML >> MD;

	for (int i = 2; i <= N; i++) dist[i] = INF;

	while (ML--) {
		int A, B, D; cin >> A >> B >> D;
		edges.emplace_back(edge(A, B, D));
	}
	while (MD--) {
		int A, B, D; cin >> A >> B >> D;
		edges.emplace_back(edge(B, A, -D));
	}
	for (int i = 1; i < N; i++) {
		edges.emplace_back(edge(i + 1, i, 0));
		edges.emplace_back(edge(i, i + 1, 1000000007));
	}
	for (int i = 1; i < N; i++) {
		for (auto &e : edges) {
			if (dist[e.x] < INF) dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
		}
	}

	bool chk = 1;
	for (auto& e : edges) {
		if (dist[e.x] < INF) if (dist[e.y] > dist[e.x] + e.d) chk = 0;
	}

	if (chk) {
		if (dist[N] > 1000000000) cout << -2;
		else cout << dist[N];
	}
	else cout << -1;
}