首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
hdu1599find专题
hdu1599find the mincost route (floyd算法,相对模板而言时间优化了一半)
Problem Description 杭州有N个景区,景区之间有一些双向的路来连接,现在8600想找一条旅游路线,这个路线从A点出发并且最后回到A点,假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区,而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线,并且花费越少越好。 Input
阅读更多...
hdu1599find the mincost route
题目大意: 在一个图里面找至少有三条边的无向环的最短路径。如果不存在有三条边以上的无向环则输出"It's impossible.". 解题思路: 带环了,所以就采用floyd算法吧,因为其它几种都是适用于单源的。 先上图; 至少三条边以上,按照一般思路的话,既然是最短路径,那我们肯定是边越少越好。但是从上图就可以看出,这个观点是显然不成立
阅读更多...