昂贵的聘礼 http://acm.pku.edu.cn/JudgeOnline/problem?id=1062
Dijkstra算法就可以了，权非负；
有的物品对应有替代品 + 优惠价格，反过来考虑，即替代物品 + 优惠价格就达到原来的物品，建图；
增加一个顶点，连接每个顶点，权值等于该顶点的价值，相当于你直接支付；
难点在于等级限制M； 枚举 + 删顶点；
因为你最后始终要到达顶点1，满足等级限制条件还要访问顶点 1？
一次枚举 (lv[1] - M) ~ lv[1]，……，lv[1] ~ (lv[1] + M) ，把不符合条件的顶点给予visit[i]=1;
Stockbroker Grapevine http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
考察flyod算法，先求出每个点到其他顶点的距离，然后选出其中的最大值，即为这个点到达所有顶点的最大距离；如果最大值为初始化的INF，则该点不能到达所有点；
然后再从能到达所有点中的集合点选出最小值；
Invitation Cards http://acm.pku.edu.cn/JudgeOnline/problem?id=1511
对SPFA邻接表实现的考察，bellman_ford,dijkstra都会超时；
求每个志愿者来回的最短路，ccs -> x -> ccs,前一部分由正向图对顶点1做一次单源最短路即可，建立逆向图再次求解就是第二部分；
Currency Exchange http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
Bellman_ford算法；从银行实现2种货币的兑换可以认为每种货币相当于一个顶点，每家银行相当于连接两个顶点的一条边；求是否存在一条路径u -> a -> b -> …… u，权值之和大于原来的值；
MPI Maelstrom http://acm.pku.edu.cn/JudgeOnline/problem?id=1502
Heavy Transportation http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
同HDU 1217
Frogger http://acm.pku.edu.cn/JudgeOnline/problem?id=2253
Til the Cows Come Home http://acm.pku.edu.cn/JudgeOnline/problem?id=2387
Wormholes http://acm.pku.edu.cn/JudgeOnline/problem?id=3259
Silver Cow Party http://acm.pku.edu.cn/JudgeOnline/problem?id=3268
Big Christmas Tree http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
Skiing http://acm.pku.edu.cn/JudgeOnline/problem?id=3037
Candies http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
Cow Hurdles http://acm.pku.edu.cn/JudgeOnline/problem?id=3615
Cow Contest http://acm.pku.edu.cn/JudgeOnline/problem?id=3660
posted on 2009-12-05 17:10
西风萧瑟 阅读(1964)
评论(0) 编辑 收藏 引用 所属分类:
图论