Tour de France

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

pair<int, int> g[37][2];
pair<int, int> rg[37][2];

int in[37];
int out[37];

int bf[37];
int ne[37];

int ans;
int n;

void sel(int a, int b){
	ne[a]=b;
	bf[b]=a;
	
	for (int j=0;j<2;j++){
		out[rg[b][j].F]--;
	}
	for (int j=0;j<2;j++){
		in[g[a][j].F]--;
	}
}

void unsel(int a, int b){
	ne[a]=0;
	bf[b]=0;
	
	for (int j=0;j<2;j++){
		out[rg[b][j].F]++;
	}
	for (int j=0;j<2;j++){
		in[g[a][j].F]++;
	}
}

int u[37];

void go(int val){
	if (val>=ans) return;
	int rdy=1;
	for (int i=1;i<=n;i++){
		if (ne[i]==0){
			rdy=0;
			if (out[i]==0) return;
		}
		if (bf[i]==0){
			rdy=0;
			if (in[i]==0) return;
		}
	}
	if (rdy){
		for (int i=1;i<=n;i++){
			u[i]=0;
			assert(bf[ne[i]]==i);
			assert(ne[bf[i]]==i);
		}
		int x=1;
		int c=0;
		while (u[x]==0){
			u[x]=1;
			c++;
			x=ne[x];
		}
		assert(c<=n);
		if (c==n){
			ans=min(ans, val);
		}
		return;
	}
	for (int i=1;i<=n;i++){
		if (ne[i]==0){
			if(out[i]==1){
				for (int j=0;j<2;j++){
					if (g[i][j].F&&bf[g[i][j].F]==0){
						sel(i, g[i][j].F);
						go(val+g[i][j].S);
						unsel(i, g[i][j].F);
						return;
					}
				}
			}
		}
		if (bf[i]==0){
			if (in[i]==1){
				for (int j=0;j<2;j++){
					if (rg[i][j].F&&ne[rg[i][j].F]==0){
						sel(rg[i][j].F, i);
						go(val+rg[i][j].S);
						unsel(rg[i][j].F, i);
						return;
					}
				}
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (ne[i]==0){
			assert(out[i]==2);
			for (int j=0;j<2;j++){
				assert(g[i][j].F>0&&bf[g[i][j].F]==0);
				sel(i, g[i][j].F);
				go(val+g[i][j].S);
				unsel(i, g[i][j].F);
			}
			return;
		}
	}
	assert(0);
}

void solve(){
	int m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		g[i][0]={0, 0};
		g[i][1]={0, 0};
		rg[i][0]={0, 0};
		rg[i][1]={0, 0};
		
		in[i]=0;
		out[i]=0;
		
		bf[i]=0;
		ne[i]=0;
	}
	for (int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a++;
		b++;
		in[b]++;
		out[a]++;
		if (g[a][0].F==0){
			g[a][0]={b, c};
		}
		else{
			assert(g[a][1].F==0);
			g[a][1]={b, c};
			if (g[a][1].S<g[a][0].S){
				swap(g[a][0], g[a][1]);
			}
		}
		
		if (rg[b][0].F==0){
			rg[b][0]={a, c};
		}
		else{
			assert(rg[b][1].F==0);
			rg[b][1]={a, c};
			if (rg[b][1].S<rg[b][0].S){
				swap(rg[b][0], rg[b][1]);
			}
		}
	}
	ans=1e9;
	go(0);
	cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED