POJ_2502_建图+最短路
POJ 2502 感觉题目意思不清晰,主要是建图,然后是最短路. 首先将速度换算成分钟,将所有输入的点都离散一下,然后处理-1 -1与一条地铁路线之间的时间(双向). 然后处理不同地铁路线之间点的距离 grid[i][j] = grid[j][i] = min(grid[i][j],dis(point[i],point[j])/v1) 12345678910111213141516171819
emerald's blog
POJ_3159_(数组模拟邻接表)
POJ 3159 题意：题目告诉我们求点1和点n之间在满足约束条件dist[a]+c>=dist[b]时的最大差值, 假设三角形abc,起点是a,a->b(2) a->c(4) b->c(3),当a点糖果数是0时,如果走a->b->c得到c糖果数为5,不满足a->c(4)的要求,所以转换为有向图,求最短路 vector邻接表不行,用数组模拟邻接表1234
POJ_1511_(dij/bellmanford)
POJ 1511 题意：求每个点去1点的时间和回来时间的最小值,回来的最短时间就是点1到每一个点的最短路径,那么每个点去点1的时间呢？单独求每个点到点1时间肯定超时 将所有有向边都反向,在求点1到每个点的最短路径就相当于去点1的时间 主要是数据量太大,只能用邻接表存图,关键在于邻接表的构建 bellmanford1234567891011121314151617181920212223242
POJ_2240_(bellmanford+floyd)/hash
POJ 2240 与POJ 1860 一样, 判断是否存在 正权环 将字符串hash成[1,30]之内的顶点, bellmanford通过松弛次数来判断是否存在环, floyd通过比较2次货币流通后的任意一点(点就是货币)的值是否增加,增加了就说明存在正环 bellmanford123456789101112131415161718192021222324252627282930313233
POJ_3660_floyd
POJ 3660 题意：告诉所有奶牛的关系,让你确定奶牛的排名(只有当该奶牛与其他所有奶牛的关系确定了才能确定该奶牛的排名) 通过floyd确定一个点是否能到另一个点.12345678910111213141516171819202122232425262728293031323334353637 #include <iostream>using namespace std;cons
POJ_1502_最短路模板
POJ 1502 题意:求最短路中的 最大值 ，模板题 dij12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 #include <iostream>#include <string.h>#include
POJ_3259_spfa
6POJ 3259 题意：能否通过负边回到过去，意思是求是否存在负权环. 开一个cnt[]记录每一个点访问的次数,如果存在负权环那么一定能一直松弛 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 #i
POJ_1860_判断正权环(bellmanford和floyd)
5POJ 1860题意：货币种类是点,货币交换是边,能否在交换回来使得金钱变多,意思就是是否存在正环 两层循环 模拟一次流通后 每一个点 的金钱数 将第一次多次循环和第二次比较，若有任意一个点钱数变多则说明存在正环123456789101112131415161718192021222324252627282930313233343536#include <iostream>usin