급하게임개발

https://www.acmicpc.net/problem/1956

이 문제의 경우 전형적인 플로이드 워셜 알고리즘을 사용 하여 구현한다
핵심이 되는  부분은

void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

k즉 i to k , k to j 즉 어떠한 정점 까지 갈때 중간에  거치는 지점이다 즉 계속 거치는 지점을 업데이트 해주면서 최소 거리를 구하는게 플로이드 워셜의 로직이다

#include <iostream>
#define INF 987654321
using namespace std;
int dp[401][401];

int v, e;
void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	int maxValue = INF;
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dp[i][j] == 0;
			else
				dp[i][j] = INF;
			
		}
	}
	for (int i = 0; i < e; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		dp[from][to] = value;
	}

	floyd();

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (dp[i][j] + dp[j][i] < maxValue && !(i==j)) {
				maxValue = dp[i][j] + dp[j][i];
			}
		}
	}
	if (maxValue >= INF) {
		cout << -1;
	}
	else {
		cout << maxValue;
	}
}