운동 - 1956

1. 개요

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

2. 코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <utility>
#define INF 987654321
using namespace std;

vector<vector<pair<int,int>>> graph;
priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
int memo[401][401];
int v, e;

void floyd_warshall() {
	
}
int main(void) {
	cin >> v >> e;
	
	fill(&memo[0][0], &memo[400][400], INF);

	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		memo[a][b] = c;
	}

	int result = INF;

	// floyd-warshall
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			for (int k = 1; k <= v; k++) {
				if (memo[j][k] > memo[j][i] + memo[i][k]) {
					memo[j][k] = memo[j][i] + memo[i][k];
					if (j == k)
						result = min(result, memo[j][k]);
				}
			}
		}
	}
	
	if (result == INF)
		printf("-1");
	else
		printf("%d", result);
	
	return 0;
}

3. 풀이 메모

플로이드-와셜 알고리즘을 변형해서 푸는 첫 문제였다. 플로이드-와셜 알고리즘을 거치면 memo[i][i]에 저장되는 값이 자기 자신으로 돌아오는데 걸리는 dist 라는 것을 이용해 문제를 푼다. 기본적으로 모든 노드를 경유 지점으로 고려하며 체크하기 때문에 이런 구현이 가능한 것으로 보인다.

4. 코멘트

플로이드-와셜 알고리즘이 생소해서 금방 풀 수가 없었다. 다른 문제도 계속해서 접하며 풀어보고 싶다.