Task: | Tour de France |
Sender: | |
Submission time: | 2017-10-17 19:06:05 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.78 s | details |
Code
#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 details
Test 1
Verdict: ACCEPTED
input |
---|
60 36 72 0 1 9990 0 2 9992 1 2 9993 ... |
correct output |
---|
359643 359649 359647 359650 359649 ... |
user output |
---|
359643 359649 359647 359650 359649 ... |
Test 2
Verdict: ACCEPTED
input |
---|
55 36 36 0 1 9999 1 2 10000 2 3 10000 ... |
correct output |
---|
359999 72 360000 88 108 ... |
user output |
---|
359999 72 360000 88 108 ... |