うんどう

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.注記

これはfloyd‐wassalアルゴリズムを変形して解いた最初の問題である.フロイド・ワッシャーアルゴリズムによりmemo[i][i]に格納された値が自分のdistに戻って問題を解決することができる.基本的に,すべてのノードが点を通過して検査されると考えられるので,この実現は可能である.

4.コメント

フロイド・ワッシャーのアルゴリズムはよく知られていないので、すぐには解けません.他の質問に触れて答えたいです.