提出 #66371240

---

ソースコード 拡げる

// 綺麗に解きなおし

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m;
  cin >> n >> m;

  // グラフを構築せず、vectorをそのまま受け取り0始まりに直しておくだけ
  vector<int> u(m), v(m), w(m);
  for (int i=0; i<m; i++) {
    cin >> u.at(i) >> v.at(i) >> w.at(i);
    u.at(i)--;
    v.at(i)--;
  }

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // 通行禁止ビットを管理する変数（ビット列と見なす）
  int forbidden = 0;

  // 上位のビットから順に確認
  for (int i=29; i>=0; i--) {

    // 仮にそのビットを禁止にしてみる
    forbidden ^= (1<<i);

    // UnionFind木を用意し、禁止されていない道だけでゴールできるか確認する
    dsu d(n);
    for (int i=0; i<m; i++) {
      if ((w.at(i)&forbidden)==0) {
        d.merge(u.at(i),v.at(i));
      }
    }

    // 禁止しちゃダメなところだった場合、禁止を解除
    if (!d.same(0,n-1)) forbidden ^= (1<<i);

  }

  // 禁止にできなかったビットを求める
  result = ((1<<30)-1)^forbidden;

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

提出情報

ジャッジ結果