문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.

  • 사이클을 이루는 정점의 비용이 최소가 되는 비용을 출력하라

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 알고리즘 문제이다.
  • 입력받기 전에 자기 자신으로 이동하는 경로의 비용은 0, 나머지는 INF로 채운다.
  • 서로 다른 정점 간 비용이 중복되지 않으므로, 입력을 받을 때 단순 저장한다.
  • 플로이드 값을 계산한다.
  • 정답값 계산
    • 사이클을 이루는 정점의 비용 == 정점 간 왕복 비용
      • 참고로, 이전에 풀었던 21940 문제와 유사하다.
    • 가지못할 경우 -1을 출력하라는 의미는 경로가 없을 수도 있다는 뜻이므로, 비교 값을 INF로 초기화해야 한다.


3. 전체 코드

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

const int INF = 0x3f3f3f3f;
int a, b, c, V, E, D[402][402];

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

	cin >> V >> E;
	for(int i=1; i<=V; i++) {
		fill(D[i]+1, D[i]+V+1, INF);
		D[i][i] = 0;
	}
	while(E--) {
		cin >> a >> b >> c;
		D[a][b] = c;
	}

	for(int k=1; k<=V; k++)
		for(int i=1; i<=V; i++)
			for(int j=1; j<=V; j++)
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

	int ans = INF;
	for(int i=1; i<=V; i++)
		for(int j=i+1; j<=V; j++)
			ans = min(ans, D[i][j] + D[j][i]);

	cout << (ans == INF ? -1 : ans);

	return 0;
}