Submission #59454165

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;

int a[11][11];
int g[11][11];

int main(){
	int n;cin>>n;
	rep(i,n)rep(j,n)cin>>a[i][j];
	int m;cin>>m;
	rep(i,m){
		int x,y;cin>>x>>y;
		x--;y--;
		g[x][y]++;
		g[y][x]++;
	}
	vector<int>p(n);
	rep(i,n)p[i]=i;
	int res=1e9;

	do{
		int cnt=0,flg=0;
		rep(i,n){
			cnt+=a[p[i]][i];
			if(i&&g[p[i-1]][p[i]])flg++;
		}
		if(!flg)res=min(res,cnt);
	}while(next_permutation(p.begin(),p.end()));
	if(res==1e9)cout<<-1<<endl;
	else cout<<res<<endl;
}

Submission Info

Submission Time
Task 032 - AtCoder Ekiden（★3）
User Rho17
Language C++ 20 (gcc 12.2)
Score 3
Code Size 632 Byte
Status AC
Exec Time 50 ms
Memory 3668 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 3 / 3
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 10_small_n_01.txt, 10_small_n_02.txt, 10_small_n_03.txt, 50_random_01.txt, 50_random_02.txt, 50_random_03.txt, 50_random_04.txt, 50_random_05.txt, 50_random_06.txt, 50_random_07.txt, 50_random_08.txt, 50_random_09.txt, 50_random_10.txt, 50_random_11.txt, 50_random_12.txt, 50_random_13.txt, 50_random_14.txt, 50_random_15.txt, 60_max_m_01.txt, 60_max_m_02.txt, 60_min_m_01.txt, 60_min_m_02.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 2 ms 3440 KiB
00_sample_02.txt AC 1 ms 3516 KiB
00_sample_03.txt AC 1 ms 3476 KiB
10_small_n_01.txt AC 1 ms 3476 KiB
10_small_n_02.txt AC 1 ms 3436 KiB
10_small_n_03.txt AC 1 ms 3408 KiB
50_random_01.txt AC 1 ms 3512 KiB
50_random_02.txt AC 1 ms 3592 KiB
50_random_03.txt AC 1 ms 3596 KiB
50_random_04.txt AC 1 ms 3456 KiB
50_random_05.txt AC 1 ms 3520 KiB
50_random_06.txt AC 1 ms 3464 KiB
50_random_07.txt AC 2 ms 3500 KiB
50_random_08.txt AC 5 ms 3668 KiB
50_random_09.txt AC 50 ms 3468 KiB
50_random_10.txt AC 50 ms 3452 KiB
50_random_11.txt AC 49 ms 3476 KiB
50_random_12.txt AC 50 ms 3572 KiB
50_random_13.txt AC 50 ms 3468 KiB
50_random_14.txt AC 49 ms 3496 KiB
50_random_15.txt AC 50 ms 3468 KiB
60_max_m_01.txt AC 50 ms 3468 KiB
60_max_m_02.txt AC 50 ms 3516 KiB
60_min_m_01.txt AC 50 ms 3476 KiB
60_min_m_02.txt AC 50 ms 3476 KiB