BOJ 1956 운동

개요

BOJ 1956 운동

• 백준 온라인 저지 1956번 문제
• BOJ 32단계

C++

#include <bits/stdc++.h>
#include <limits.h>
#define INF 12345678
using namespace std;

int V, E;
int A[401][401];

int solve() {
    int ans = INF;
	for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (A[i][k] + A[k][j] < A[i][j]) {
					A[i][j] = A[i][k] + A[k][j];
				}
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i == j) continue;
			ans = min(ans, A[i][j]+ A[j][i]);
		}
	}
	return (ans == INF) ? -1 : ans;
}

int main() {
	cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			A[i][j] = INF;
		}
	}
	int a, b, c;
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		A[a][b] = c;
	}
	cout << solve();
}