문제 출처

1. 문제설명

• 플로이드-워셜 값이 주어진다.
• 어떤 정점에서 시작해서 모든 정점을 방문해야 한다.

• 최소 비용을 구하라

• 문제 분류
  • Graph, Floyd

2. 알고리즘 설계

• 플로이드 값을 역탐색하는 문제이다.
• 문제를 풀이할 때 정말 난해했던 부분은, 말이 안되는 경우가 포함되어 있었다는 것이다.
  • D[i][j] > D[i][k]+D[k][j]
  • i->j로 가는 경로와 i->k->j 경로라는 의미인데,
  • 생각해보면, 플로이드를 갱신할 때 위의 조건이면 이미 값이 갱신되었어야 했다.
  • 최단 경로이므로.. 그래서 이러한 경우는 말이 안되는 경우이다.
  • 문제에서 대놓고 -1을 출력하라고 명시가 되어있었다.
• 말이 안되는 경우를 배제했으니, 최단 경로를 구해야 한다.
• D[i][j] > D[i][k]+D[k][j] 이건 말이 안되지만, D[i][j] == D[i][k]+D[k][j] 이건 말이 된다.
  • 다만, D[i][j]는 두 개의 정점을 방문한 비용이고 우항은 3개의 정점을 방문한 비용이다.
  • 즉, 우항이 더 이득이라는 뜻이므로 D[i][j]의 경로를 OFF한다.
    • 표현이 좀 이상한데, 비용을 더할 때 더하지 않는다는 뜻이다.
• OFF된 경로를 제외한 모든 비용을 더해준다.
• 테스트 케이스를 보면 대각선을 기준으로 대칭인 그래프이다.
  • 즉, 우리는 같은 비용을 두번씩 더했다.
  • 결과값/2가 우리가 찾던 정답값이 된다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f, SZ = 20;
int n, D[SZ][SZ], ans;
bool tmp[SZ][SZ];

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);

	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==j || j==k || i==k) continue;

				if(D[i][j] > D[i][k]+D[k][j]) { 	// 말이 안되는 경우
					cout << -1;
					return 0;
				}

				// 한번에 3개의 노드를 처리할 수 있으니, 기존 2개는 처리
				if(D[i][j] == D[i][k]+D[k][j]) tmp[i][j] = true;
			}

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			ans += (!tmp[i][j] ? D[i][j] : 0);

	// 경로가 양방향인데 양방향 모두 계산했음.
	cout << ans / 2;

	return 0;
}