글 읽기 - 벨만-포드 알고리즘 질문입니다.

adfsfsf 5년 전 0

문제를 벨만-포드 알고리즘으로 풀었는데 어디서 잘못된 것인지 알고 싶습니다. 반례가 있다면 알고 싶습니다.

#include <iostream>
using namespace std;
int main(void)
{
	int t, n, m, i, j, k, c, d, e, ch, max = 0;
	long int **a, *b, **check;//a는 데이터 저장, check는 케이스 저장, b는 각 사람 별 최솟값
	cin >> t;
	for (i = 0; i < t; i++)
	{
		cin >> n >> m;
		a = new long int *[m];
		for (j = 0; j < m; j++)
			a[j] = new long int[m] {0};
		b = new long int[m];
		check = new long int *[m];
		for (j = 0; j < m; j++)
			check[j] = new long int[m] {0};
		for (j = 0; j < m; j++)
			b[j] = -1;//모든 사람과의 거리를 -1(무한)으로 초기화
		for (j = 0; j < n; j++)
		{
			cin >> c >> d >> e;
			a[c][d] = e;//c가 d를 알 때 거리는 e
		}
		b[0] = 0;//자기 자신의 거리는 0
		for (j = 0; j < m; j++)//0번이 아는 사람들 부터 확인
		{
			for (k = 0; k < m; k++)
			{
				if (a[j][k] != 0)//j가 k를 알 때
				{
					if (b[j] != -1)//0이 j를 알 고 있을 때
					{
						if (b[k] == -1||(b[k]>(b[j]+a[j][k])))//k를 모르는 상태 또는 k를 이미 알고 있지만 j를 거치는 것이 더 빠르면
						{
							b[k] = (b[j] + a[j][k]);//j와의 거리 + j와k의 거리가 k까지의 거리
							for (ch = 0; ch < m; ch++)
							{
								check[k][ch] = check[j][ch];//k까지의 경로를 j까지의 경로로 설정
								max = check[k][ch] > max ? check[k][ch] : max;
							}
							check[k][j] = max + 1;//k를 마지막 방문 지점으로 설정
						}
					}
				}
			}
		}
		max = 0;
		cout << "Case #" << i + 1 << ":";
		for (ch = 0; ch < m; ch++)
		{
			for (j = 0; j < m; j++)
			{
				if (check[m - 1][j] == ch + 1)//최고 위원까지 도달하는 경로를 순서대로 출력
				{
					max = 1;
					cout << " " << j;
					break;
				}
			}
		}
		if (max == 1)//경로가 있었음을 의미
			cout << " " << m - 1 << endl;
		else//경로가 없었음을 의미
			cout << " -1" << endl;
	}
	return 0;
}

uss425 2년 전 0

좀 오래된 글이지만 답변 남깁니다.

u와 v가 친구이면, v와 u와도 친구이므로 양방향 간선으로 구성해주셔야 합니다.

그것만 수정해주시면 될 것 같네요..

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

문제

문제

출처

ICPC

벨만-포드 알고리즘 질문입니다.

adfsfsf 5년 전 0

uss425 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말