BOJ 1219 오민식의 고민

사용한 알고리즘

벨만포드 알고리즘, DFS

알고리즘 설명

각 도시에 도착한 경우 얻는 돈과 버스를 타고 갈때에 드는 돈을 생각해야한다.
먼저 각 도시에 도착한시에 얻을 수 있는 돈을 city에 저장한다.
다음 각 도시을 연결하는 버스와 가격을 저장한다.
이 뒤에 연결되어 있는 버스들을 시작점으로 부터 벨만포드 알고리즘을 적용한다.
여기서 연결되지 않는 경우에는 dist(도착점)의 값이 무한대의 값이다. 이때에 “gg”를 출력한다.
다음 벨만포드 알고리즘에서 N번재 edge를 업데이트 하는 경우는 음의 사이클 조건이다. 고로 이 음의 사이클과 연결되어 있는 노드를 cycle로 연결시킨다.
도착점이 이 음의 사이클에 포함되어 있는 경우 “Gee”를 출력한다.
위 두 경우가 아닌 경우 도착점의 이윤을 출력한다.

풀이

// baekjoon 1219 yechan
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N=101;
const int MAX_INF=2e9;

int N, S, E, M, city[MAX_N], dist[MAX_N], cycle[MAX_N];
vector<pair<int, int> > adj[MAX_N];

int dfs(int here) {
	cycle[here] = true;
	for (int i=0; i<adj[here].size(); i++) {
		int nx = adj[here][i].first;
		if (cycle[nx]) continue;
		dfs(nx);
	}
}

int main() {
	scanf("%d%d%d%d", &N, &S, &E, &M);
	while (M--) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(make_pair(v, w));
	}
	for (int i=0; i<N; i++)
		scanf("%d", &city[i]);

	fill(dist, dist+MAX_N, MAX_INF);

	dist[S]=-city[S];
	for (int i=0; i<N*2; i++) {
		for (int j=0; j<N; j++) {
			if (dist[j] == MAX_INF) continue;
			for (int k=0; k<adj[j].size(); k++) {
				int nx = adj[j][k].first;
				int nw = adj[j][k].second;
				if (dist[nx] > dist[j] + nw - city[nx]) {
					dist[nx] = dist[j] + nw - city[nx];
					if (i == 2*N - 1) {
						dfs(j);
					}
				}
			}
		}
	}

	if (dist[E] == MAX_INF) {
		printf("gg\n");
	}
	else if (cycle[E]) {
		printf("Gee\n");
	} else {
		printf("%d\n", -dist[E]);
	}

	return 0;
}