글 읽기 - 92%에서 자꾸 틀렸다고 나오는데 도와주실 분 계신가요...

jduck1024 2년 전 0

사이클이 발생하지 않는 경우

- 종료지점으로 가는 길이 있는 경우 : 답 출력

- 종료지점으로 가는 길이 없는 경우 : -1 출력

사이클이 발생하는 경우

- 종료지점으로 가는 길에 있는 경우 : -1 출력

- 종료지점으로 가는 길에 없는 경우 : 답 출력

특정 노드가 어느 노드로부터 왔는지 검사하며 스택에 넣는 과정에서 사이클 발견 시 실행을 멈추는 방향으로 구현해봤는데 자꾸 틀렸다고 뜹니다.

혹시 어느 부분이 잘못되었는지 아는 분 계시면 알려주시면 감사하겠습니다ㅠㅠ

#include <iostream>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

struct Node {
	int key;
	int value;
	Node(int k, int v) {
		key = k;
		value = v;
	}
};

int n;
int m;
vector<Node> arr[101];
long long cost[101];
int from[101];
bool isCycle[101]{ false, };
stack<int> s;

int main() {
	for (int i = 0; i < 101; i++) {
		cost[i] = LLONG_MIN;
	}

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int start;
		int end;
		int val;

		cin >> start >> end >> val;
		arr[start].push_back(Node(end, val));
	}

	cost[1] = 0;
	// 벨만 포드
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < arr[j].size(); k++) {
				Node node = arr[j].at(k);
				int key = node.key;
				int value = node.value;

				if (cost[j] != LLONG_MIN && cost[j] + value > cost[key]) {
					cost[key] = cost[j] + value;
					from[key] = j;

					if (i == n - 1) {
						// cycle 발생 지점 저장
						isCycle[j] = true; 
						isCycle[key] = true;
					}
				}
				else {
					if (cost[j] == LLONG_MIN && j == key) {
						cost[key] = value;
					}
				}
			}
		}
	}

	// 목적지까지 가는 경로 없을 경우
	if (from[n] == LLONG_MIN) {
		cout << -1 << endl;
		return 0;
	}

	int i = n;
	while (true) {
		// 목적지와 연결된 사이클이 있을 경우 -1 출력
		if (isCycle[i]) {
			cout << -1 << endl;
			return 0;
		}
		s.push(i);

		if (i == 1) {
			break;
		}

		i = from[i];
	}

	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

92%에서 자꾸 틀렸다고 나오는데 도와주실 분 계신가요...

jduck1024 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말