글 읽기 - 플로이드 와샬을 이용한 문제풀이 중 질문입니다.!

his130 6년 전 0

일단 아래와 같이

주어진 값에 대해서 플로이드 알고리즘을 다시 해서

i - j 까지 경로가 있을 때, i - k - j 로 갈 수 있다면, i - j 를 삭제 하는 코드입니다.

궁금한 점은 주석으로 된 부분입니다.

대부분 사람들이 사용하지 않는 간선을 삭제해서 푸는데요,

저는 처음에 사용하는 간선을 체크해서 문제를 풀었습니다.

근데 그렇게 풀 경우 답이 나오지 않더라구요...

사용하지 않는 간선 삭제랑, 사용하는 간선의 값의 합을 출력하는거랑...

왜 틀린걸까요? 어떤 로직상의 문제점이 있는걸까요?

#include<iostream>

using namespace std;
int D[21][21];
const int INF = 987654321;
bool unuse[21][21];
int main()
{
	//freopen("input.txt", "r", stdin);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> D[i][j];
		}
	}


	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i!=k && j!=k && i!=j)
				{
					if (D[i][j] == D[i][k] + D[k][j])
					{
						unuse[i][j] = true;
						//unuse[i][k] = false;
						//unuse[k][j] = false;
					}
					else if(D[i][j] > D[i][k] + D[k][j])
					{
						printf("-1\n");
						return 0;
					}
					/*
					else if(D[i][j] < D[i][k] + D[k][j])
					{
						//unuse[i][j] = false;
						unuse[i][k] = true;
						unuse[k][j] = true;
					}
					*/
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			if (unuse[i][j]==false)
			{
				ans += D[i][j];
			}
		}
	}

	cout << ans << endl;

	return 0;
}

his130 6년 전 1

자문자답

else if(D[i][j] < D[i][k] + D[k][j])
{
//unuse[i][j] = false;
unuse[i][k] = true;
unuse[k][j] = true;
}

이 케이스에서 i-k 간선과 k-j 간선이 쓰이지 않는다고 할 수 없습니다.

존재 하면 다른 정점끼리의 플로이드 알고리즘을 사용할 때 사용될 수도 있고,

삭제 된다면, for문을 돌면서 자신의 차례에 삭제가 되기 때문입니다.

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

문제

문제

출처

ICPC

플로이드 와샬을 이용한 문제풀이 중 질문입니다.!

his130 6년 전 0

his130 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말