글 읽기 - 플로이드 워셜 질문

ondal1997 4년 전 0

아래 코드가 왜 안 돌아가는지 정말 모르겠습니다. 너무 화가 납니다. 누군가 제발 알려줬으면 한이 풀릴 것 같습니다. 키보드뿌쎠뻐릴껐만깥쓰ㅃ니다.

#include <iostream>

using namespace std;

int main()
{
	int N;

	cin >> N;

	int times[20][20];

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> times[i][j];
		}
	}

	for (int k = 0; k < N; ++k)
	{
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (k == i || k == j || i == j) continue;

				if (times[i][j] > times[i][k] + times[k][j])
				{
					cout << -1 << endl;

					return 0;
				}
			}
		}
	}

	for (int k = 0; k < N; ++k)
	{
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (k == i || k == j || i == j) continue;

				if (times[i][j] == times[i][k] + times[k][j])
				{
					times[i][j] = 0;
				}
			}
		}
	}

	int sum = 0;

	for (int i = 0; i < N; ++i)
	{
		for (int j = i + 1; j < N; ++j)
		{
			sum += times[i][j];
		}
	}

	cout << sum << endl;
}

kibbomi 4년 전 1

글쓴이님 께서 올리신 코드의 floyd에서 길이 존재하지않는 즉, 거리가 0인 부분은 if - continue문을 통해서 접근하지 못하도록 해 놓으셨습니다.

하지만 두번쨰 floyd에서 윗분이 말씀해주셨듯이, 거리를 0으로 변경해버리면 추후 계산에 문제가 생기게 됩니다.

예를 들면 정점 k=1을 지날때 어떤 부분의 값을 0 으로 변경해주고, k=2 계산할때에 마치 두 정점간의 거리가 0인것처럼 보인다는 것입니다.

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

문제

문제

출처

ICPC

플로이드 워셜 질문

ondal1997 4년 전 0

kibbomi 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말