글 읽기 - 벨만포드 여러 반례넣어도 잘 실행되는것 같은데 어디가 문제인건지 모르겠습니다

gyoo21w 5년 전 0

잘 모르겠어서 구글링하면서 이런 저런 코드 보고 짜집기하듯이 해서

어느정도 이해하고 작성했는데, 제가 놓친 조건이 어디있는지 모르겠습니다

코드가 잘못된 부분이 있는지, 반례가 있는지 찾아주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#define N_CITY 501
#define INF 10001
using namespace std;
int _n_city, _m, dist[N_CITY];
vector<pair<int, int> > V[N_CITY];
void InitArr() { 
	for (int i = 1; i <= _n_city; i++){
		dist[i] = INF;
	}
}
int main()
{
	cin >> _n_city >> _m;
	InitArr();
	for (int i = 0; i < _m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		V[from].push_back(pair<int, int>(to, cost));
	}
	dist[1] = 0;
	bool cycle = false;
	for (int i = 1; i <= _n_city; i++) {
		for (int j = 1; j <= _n_city; j++) {
			for (int k = 0; k < V[j].size(); k++) {
				int next_city = V[j][k].first;
				int next_weight = V[j][k].second;
				if ((dist[j] != INF) && (dist[next_city] > dist[j] + next_weight)) {
					dist[next_city] = dist[j] + next_weight;
					if (i == _n_city) { cycle = true; }
				}
			} 
		}
	}
	if (cycle) { cout << "-1" << endl; }
	else {
		for (int i = 2; i <= _n_city; i++) {
			if (dist[i] == INF) dist[i] = -1;
			cout << dist[i] << endl;
		}
	}
	return 0;
}

/*

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

*/

gaelim 5년 전 1

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

도시 500개의 dist 최대경로는 499 간선길이입니다. 이 때, 대충 500*10,000 = 500만 입니다. INF값이 너무 작은것같습니다.

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

문제

문제

출처

ICPC

벨만포드 여러 반례넣어도 잘 실행되는것 같은데 어디가 문제인건지 모르겠습니다

gyoo21w 5년 전 0

gaelim 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말