perogram

No.845 最長の切符 ~最長距離・ダイクストラ・ベルマンフォード・bit DP~

Quiz

AC

https://yukicoder.me/submissions/405827

解法

// i : また訪れてない頂点フラグ
// j : 現在地
// とした場合の最長距離
int dp[1<<16][16];
  • としてbit DP

以下、(間違った考え方による)試行錯誤

最長距離をダイクストラで求める!?

f:id:peroon:20191207101115p:plain

5 6
5 3 14284
5 4 7227
2 5 36216
2 1 29991
5 1 49500
4 3 2748
  • これはとあるテストケース
  • 眺めると、2-1-5-3-2と進むのが最長で、答えは96523
  • これをコストに-1をかけて頂点2からダイクストラすると、

f:id:peroon:20191207101505p:plain

  • まず最短距離で行ける5がfixする
  • 次に、最短距離で行ける1がfixする
  • 1から5に行けばより最短距離だが、ダイクストラは近くの点から最短距離をfixさせていき、上書きはしないアルゴリズムなので、2-1-5のパスで上書きされることはなく、正しい解も求まらない

最長距離をベルマンフォードで求める!?

  • ではベルマンフォードならどうか?
  • こちらは上書きを繰り返していくアルゴリズム
  • しかし、上図を見ればわかるように、負の閉路が存在するので解は-infとなり、こちらも正しい解は求まらない