032.md

032 - AtCoder Ekiden (★3)

解答

#include <iostream>
#include <vector>
#include <numeric> // std::iota()
#include <algorithm> // std::min(), std::next_permutation()

// 現在の走順でタスキを受け渡し可能であるかを返す
bool IsValid(const std::vector<int>& runners, const std::vector<std::vector<bool>>& relation)
{
	for (int i = 0; i < (runners.size() - 1); ++i)
	{
		// 渡す人
		const int from = runners[i];
		
		// 渡される人
		const int to = runners[i + 1];

		if (!relation[from][to]) // 受け渡し不可だったら
		{
			return false;
		}
	}

	return true;
}

int main()
{
	// N 人の選手
	int N;
	std::cin >> N;

	// 時間の情報 (N 区分の vector が N 人分)
	std::vector<std::vector<int>> A(N, std::vector<int>(N));
	for (auto& aa : A)
	{
		for (auto& a : aa)
		{
			std::cin >> a;
		}
	}

	// タスキを受け渡し可能であるかの情報 (相手 N 人分の vector が N 人分), 初期値はすべて true
	std::vector<std::vector<bool>> relation(N, std::vector<bool>(N, true));

	// M 個の相性
	int M;
	std::cin >> M;
	
	// タスキの受け渡し不可情報の登録
	for (int i = 0; i < M; ++i)
	{
		int X, Y;
		std::cin >> X >> Y;
		relation[X - 1][Y - 1] = false;
		relation[Y - 1][X - 1] = false;
	}

	// 走順のパターン
	std::vector<int> runners(N);
	// 順列のために, 初期値を埋める
	// 例: N = 4 のとき { 0, 1, 2, 3 } になる
	std::iota(runners.begin(), runners.end(), 0);

	// これ以上の時間はかからない時間
	const int initialTime = (1000 * N + 1);
	
	// 最小の時間
	int minTime = initialTime;

	do
	{
		if (!IsValid(runners, relation)) // 走順が NG ならスキップ
		{
			continue;
		}

		// 現在の走順での合計時間
		int time = 0;

		// 区
		int stage = 0;

		// 各走者について
		for (const auto& runner : runners)
		{
			// その走者が, その区を走るのにかかる時間を加算
			time += A[runner][stage];
			
			// 次の区へ
			++stage;
		}

		// 最小の時間を更新
		minTime = std::min(minTime, time);

	} while (std::next_permutation(runners.begin(), runners.end())); // 順列

	if (minTime == initialTime) // 走順が成立不可だった場合
	{
		minTime = -1;
	}
		
	std::cout << minTime << '\n';
}