ここから本文です

bitDP http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3519506#1

hat********さん

2019/5/222:00:03

bitDP
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3519506#1

36行目でコメントアウトしている部分が入らない理由を教えてください。
vはその集合で最後に訪れたとこなので、vが集合に入ってないとまずいと思います。

閲覧数:
31
回答数:
1

違反報告

ベストアンサーに選ばれた回答

プロフィール画像

カテゴリマスター

cd6********さん

2019/5/307:31:36

S の各ビットが訪問済みかどうかを表しています。
3 点で考えると 2 進数で S = 111 はすべて未訪問
S = 110 は 0 番目を訪問、S = 100 は 0、1 番目を訪問など。
S >> v & 1 は v 番目が未訪問のとき真なので
!(S >> v & 1) は v 番目を訪問済みのとき真です。
距離最小を求めたいんだから訪問済みをスキップするとまずいです。
一方 !(S >> u & 1) の方は u 番目を訪問済みでないと
v-u 間の距離を使って最小距離を求められません。

質問した人からのコメント

2019/5/9 13:55:49

ありがとうございました。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる