[POJ3268]Silver Cow Party[SPFA]

题面

这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址