HDU 1599 find the mincost route
昨天晚上从Yasola那里偷来的一道题…… 为什么Yasola这么优秀啊！！！！！ 求求你别学了，我已经完全跟不上了…… 因为看着题目并不是很难我也就写了一蛤，然后自以为是无脑题就疯狂WA…… emmmm…… 其实仔细想想还是挺简单的。 题意： 给你一张无向图，要你找出最小环。 点数 ( n \leq 100 ) 思路： 对 floyd 进行简单增加一点代码。 floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前，将其固定为环上的一个点，这点必定不会被所有最短路夹在中间。 有一个非常显然的问题就是，当我固定一个中间结点的时候，我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。 比如说 存在一个 ABCA 的环与一个 BCDB，其中 ( BD + DC < BC , AB + AC < BC )，而当我使 A 为固定结点，而我的 D 还不曾成为固定结点，也就不会被加入 BC 的最短路。 然而实际上并不要担心，…