Submission #63545035

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
#define pcnt __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
const ld eps = 1e-10;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
#define pcnt __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
const ld eps = 1e-10;
const ll INF = 1e18; 
ull mo = 1000000007;
ld PI=asin(1)*2;
//using namespace atcoder;

template<typename F>
void all_permutations(ll n,F f){
  vector<ll> vs(n);
  iota(vs.begin(),vs.end(),0);
  do f(vs); while(next_permutation(vs.begin(),vs.end()));
}
// https://atcoder.jp/contests/abc326/submissions/47026496 abc326_d

int main(){
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> G(N, vector<ll>(N, -1));
    rep(i,M){
        ll u,v,w;
        cin >> u >> v >> w;
        u--;v--;
        G[u][v] = w;
        G[v][u] = w;
    }
    ll ans = 2e18;
    auto f = [&](vector<ll>& vs){
        if(vs[0] != 0) return;
        ll t = 0;
        rep(i,N-1){
            ll pr = vs[i];
            ll nx = vs[i+1];
            if(G[pr][nx] == -1) return;
            t ^= G[pr][nx];
            if(nx == N-1) break;
        }
        cmin(ans, t);
        return;
    };
    all_permutations(N,f);
    cout << ans << endl;
}

Submission Info

Judge Result