AtCoder Beginner Contest 073 D - joisino's travel

全頂点が最大200個なのでワーシャルフロイド法を使うことができる。立ち寄る頂点の順番についても最大8個なので next_permutation が使える。便利〜〜〜〜。

ハイライト

  warshall_floyd();

  int ans = LINF;  
  do {
    int tmp = 0;
    REP(i,R-1) tmp += d[r[i]][r[i+1]];
    ans = min(ans,tmp);
  } while (next_permutation(ALL(r)));

ワーシャルフロイド法をスニペット化した。

コスト入力時の無向・有向の区別で一瞬詰まった。

なお next_permutation はソート済みである必要がある。