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

Quiz

• No.845 最長の切符 - yukicoder
• https://yukicoder.me/problems/no/845

AC

https://yukicoder.me/submissions/405827

解法

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

• としてbit DP

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

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

• 最短距離はダイクストラで求まるのだから、コストに-1をかけてダイクストラすればいいのでは？
• それはダメ。なぜかというと、

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からダイクストラすると、

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

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

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

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～