글 읽기 - [C++] 1865 11%에서 틀렸습니다가 나옵니다.

so4644009 4년 전 0

음수 사이클을 발견하면 YES를, 아니면 NO를 출력하는 걸로 생각했는데 틀렸습니다가 나옵니다. 접근 방식에 문제가 있는 것 같아서 1시간 가까이 고민해봤는데 도무지 모르겠습니다. 접근방식에 대한 힌트 좀 주실 수 있나요?

#include <stdio.h>
#include <utility>
#include <vector>
#define MAX 510
#define INF 2*1e9
using namespace std;

vector<pair<int, int>> v[MAX];
int dist[MAX];
bool cycle;
int n;

void bellman_ford(const int end) {
	size_t i, j;
	for (i = 1; i <= n; ++i)
		for (j = 1; j <= n; ++j)
			for (auto check : v[j])
				if (dist[j] != INF && dist[check.first] > check.second + dist[j]) {
					if (i == n) cycle = 1; // 음수 사이클이 있으면 cycle을 true로 
					dist[check.first] = dist[j] + check.second; 
				}
	return;
}

int main(void) {
	int tc;
	int m, w;
	int s, e, t;
	size_t i;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d %d %d", &n, &m, &w);
		fill(dist, dist + n + 1, INF);
		dist[1] = 0;
		cycle = 0;
		for (i = 0; i < MAX; ++i) v[i].clear();
		while (m--) {
			scanf("%d %d %d", &s, &e, &t);
			v[s].push_back(make_pair(e, t));
		}
		while (w--) {
			scanf("%d %d %d", &s, &e, &t);
			v[s].push_back(make_pair(e, -t));
		}
		bellman_ford(n);
		puts(cycle ? "YES" : "NO");
	}
	return 0;
}

lucian0910 4년 전 1

도로는 양방향이라고 되어있는데 위 코드를 보면 한 방향으로만 적용되어있습니다. 양방향으로 갈수 있게 도로 정보를 추가한다면 바로 정답이 나오실 겁니다.

so4644009 4년 전 0

감사합니다.

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

문제

문제

출처

ICPC

[C++] 1865 11%에서 틀렸습니다가 나옵니다.

so4644009 4년 전 0

lucian0910 4년 전 1

so4644009 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말