D. Shortest Cycle

Quiz

https://codeforces.com/contest/1206/problem/D

  • 2000人が解いているので解けなきゃいけない

Submit

なし

解法

f:id:peroon:20190912030027p:plain

  • それ以外の場合、同じビット位置が1のものの数は多くても2
  • a=1018なので、ビットは60桁まで考えれば十分で、エッジの数も60以下となり、グラフはとても小さい
  • 以下を考える

f:id:peroon:20190912030414p:plain

  • この場合、最小のサイクルは4
  • これをどう見つけるかだが、各エッジ edge(u, v) を切ってみて、それでもu-v間にinf以外の最短距離があるか調べる
  • 最短距離がある場合
    • サイクルの長さ = 最短距離 + 1
  • 最短距離がない(inf)場合
    • そのエッジはサイクルと関係ない
  • よって、求めることができました