취미로 코딩하기

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

이번에 볼 문제는 백준 6002번 문제인 Job Hunt이다.
문제는 아래 링크를 확인하자.

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

한 번의 이동으로 D원을 벌고 그 이동에 드는 비용만큼을 지불하는 그래프를 만들고, 출발 도시 S에서 각 도시로 이동할 시 가장 많은 돈을 갖고 도착하게 되는 경로를 찾는 문제를 생각하자. 이 때 문제의 답은 이러한 도착 도시 중 가장 많은 돈을 가진 상태로 도착한 도시 찾는 것으로 구할 수 있다.

S에서 출발하여 돈을 무한히 벌 수 있는 사이클로 올라갈 수 있다면 -1을 출력해주자.

출발점에서도 돈을 벌고 다음 도시로 이동할 수 있다는 점에 유의하자.

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

#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[221];
vector<edge> edges;

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

	int D, P, C, F, S; cin >> D >> P >> C >> F >> S;
	while (P--) {
		int x, y; cin >> x >> y;
		edges.emplace_back(edge(x, y, -D));
	}
	while (F--) {
		int x, y, d; cin >> x >> y >> d;
		edges.emplace_back(edge(x, y, d - D));
	}
	
	for (int i = 1; i <= C; i++) dist[i] = 1000000007;
	dist[S] = -D;

	for (int i = 1; i < C; i++) {
		for (auto e : edges) {
			if (dist[e.x] < 1000000007) {
				dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
			}
		}
	}

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

	if (chk) {
		ll ans = dist[1];
		for (int i = 2; i <= C; i++) {
			if (dist[i] < ans) ans = dist[i];
		}
		cout << -ans;
	}
	else cout << -1;
}