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

(追記) (追記ここまで)

플로이드 워셜 질문

1507번 - 궁금한 민호

ondal1997 6년 전 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 5년 전 1

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

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC