앳코더90 - 032 - AtCoder Ekiden（★3）

https://atcoder.jp/contests/typical90/tasks/typical90_af

032 - AtCoder Ekiden（★3）

 

31번은 스프라그 그런디 문제 같은데 문제 이해가 잘 안되서 일단 킵이다. N명의 선수가 주어지고 바통달라기를 한다. N^2의 행렬로 세로는 N번째 선수가 가로는 N번째 구간을 가는데 걸리는 시간을 의미한다.

1 10 100

10 1 100

100 10 1 

이라면 1번선수는 1번구간 2번구간 3번구간을 가는데 1 10 100 만큼 시간이 든다.

M개의 줄에 같이 있으면 안되는 쌍이 나온다. 1 2 라고 하면 1번선수랑 2번선수가 붙어있으면 안된다. 이때, 마지막 구간까지 바통을 받아 완주할 때 최소 시간을 구하라.

 

처음에는 이게 왜 별 3개짜리지 싶었다. 핵심이 M인데, 같이 있으면 안되는 쌍이 있다면 누가 먼저 시작하게하고 나중에 처리를 해줘야 하나 했는데, 다시 N을 보니 N이 10이다. 그리고 브루트포스임을 깨닫게 되었다.

 

N!에서 M의 규칙을 어기는 값만 제거해주면 되는것이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, M;
int arr[12][12];
set<pii> s;
vector<vector<int>> comb;
vector<int> hubo;
int visited[12];

void dfs()
{
	if (hubo.size() == N)
	{
		bool pos = true;
		for (int i = 0;i < N - 1;i++)
		{
			int a = hubo[i];
			int b = hubo[i+1];

			if (s.find({ a,b }) != s.end() || s.find({b, a}) != s.end())
			{
				pos = false;
				break;
			}
		}

		if (pos)
		{
			comb.push_back(hubo);
		}

		return;
	}

	for (int i = 1;i <= N;i++)
	{
		if (visited[i])
			continue;

		hubo.push_back(i);
		visited[i] = 1;
		dfs();
		hubo.pop_back();
		visited[i] = 0;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	rep(i, N)
	{
		rep(j, N)
		{
			cin >> arr[i][j];
		}
	}

	cin >> M;

	rep(i, M)
	{
		int a, b;
		cin >> a >> b;
		if (a > b)
			swap(a, b);
		s.insert({ a,b });
	}

	dfs();

	int ans = INF;
	rep(i, comb.size())
	{
		int p = 0;
		auto cur = comb[i];
		int pos = 0;
		for (auto j : cur)
		{
			p += arr[j - 1][pos++];
		}
		ans = min(ans, p);
	}

	if (ans == INF)
		cout << -1;
	else
		cout << ans;

	return 0;
}