글 읽기 - 그래프 문제 질문합니다.

sgc109 7년 전 0

단순히 플로이드로 도달가능성을 인접행렬로 구해놓고

벨만포드 에서 식을 조금 변형시켜서(도시에서 벌어들이는 수입도 같이계산)

음수 사이클이 있을경우 시작지점부터 음수사이클로 도달가능한지, 그리고 음수사이클부터 도착지점까지 도달 가능한지를

체크해서 가능해면 Gee 불가능하면 시작지점부터 도착지점까지 최단거리, 그리고 애초에 시작점에서 도착점까지 도달불가능하면 gg 를

출력하도록 코드를 작성해서 제출을 해봤는데 22%에서 틀렸습니다. 가 뜨는데

제가 간과한 부분이 어떤건지 잘 모르겠습니다. 애초에 중요한걸 빠뜨린 걸까요?

@kcm1700 조언주시면 감사드리겠습니다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#define REP(i,a,b) for(int i = a; i < b; ++i)
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> ii;

const int MAX_V = 100;
const int INF = 0x3a3a3a3a;

int nodeCost[MAX_V];
vector<int> upper;
vector<vector<ii> > adj;
bool reachable[MAX_V][MAX_V];

int N,M,S,F;

void floyd() {
	FOR(k,N) {
		FOR(i,N) {
			FOR(j,N) {
				reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j]);
			}
		}
	}
}

bool bellman(int start) {
	upper[start] = -nodeCost[start];
	FOR(k,N-1) {
		bool updated = false;
		FOR(here,N) {
			FOR(i,adj[here].size()) {
				int there = adj[here][i].first;
				int dist = adj[here][i].second;
				if(upper[there] > upper[here] + dist - nodeCost[there]) {
					upper[there] = upper[here] + dist - nodeCost[there];
					updated = true;
				}
			}
		}
		if(!updated) return false;
	}
	
	// bool updated = false;
	FOR(here,N) {
		FOR(i,adj[here].size()) {
			int there = adj[here][i].first;
			int dist = adj[here][i].second;
			if(upper[there] > upper[here] + dist - nodeCost[there]) {
				upper[there] = upper[here] + dist - nodeCost[there];
				if(reachable[S][here] && reachable[here][F]) return true;
			}
		}
	}
	return false;
}

int main() {
	scanf("%d%d%d%d",&N,&S,&F,&M);
	adj = vector<vector<ii> >(N, vector<ii>());
	upper = vector<int>(N,INF);
	FOR(i,N) {
		FOR(j,N) {
			if(i==j) reachable[i][j] = true;
			else reachable[i][j] = false;
		}
	}
	FOR(i,M) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		adj[a].pb(mp(b,c));
		reachable[a][b] = true;
	}
	FOR(i,N) {
		scanf("%d",nodeCost+i);
	}
	floyd();
	bool isThereCycle = bellman(S);
	if(!reachable[S][F]) printf("gg");
	else if(isThereCycle) printf("Gee");
	else printf("%d",-upper[F]);

	return 0;
}