Charlesss

ACM_最短路

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章 / ACM_最短路（共14篇）

POJ 2387 Til the Cows Come Home(Dijkstra模板题)

题目链接：http://poj.org/problem?id=2387 题意是输入n条边，m个城镇，然后输入a城镇到b城镇的距离，最后问从n到1城镇的最短距离为多少。最短路的入门题吧，直接用迪杰斯特拉的模板就行了，需要注意的是有一个判重，这个代码中注释的有，看一下就明白了。 AC代码...

2018-07-26

0 452

POJ 2253 Frogger(变形Floyd)

题目链接：http://poj.org/problem?id=2253 题意是一只青蛙在湖中一颗石头上，它想去有另一只青蛙的石头上，但是湖里的水很脏，它不愿意游泳，所以它要跳过去；给出两只青蛙所在石头的坐标，及湖里其他石头的坐标；任一两个坐标点间都是双向连通的。显然...

2018-07-26

0 582

POJ 2240 Arbitrage(Floyd)

题目链接：http://poj.org/problem?id=2240 题意是给了n种货币，m种汇率，然后问能不能经过一系列的转换后使钱增值。我们可以用Floyd算法去更新每两种货币间能获得的最大价值，就是更新max(A->C , A->B * B...

2018-07-26

0 474

POJ 3660 Cow Contest(Floyd+传递闭包)

题目链接：http://poj.org/problem?id=3660 题意是有n头牛，然后有m次操作，每次操作有两个数表示A可以打败B，然后要给这n头牛排名，问可以确定几头牛的名次时确定的。对于一头牛的排名我们需要知道有多少头牛(i)能打败我，我又能打败多少...

2018-07-25

0 469