思路:以物品为结点,物品之间的优惠价格为边权值建图,酋长10000金币当做0号结点,题意就是求图中各结点到0号结点的最短路长度,再加上终点处物品的价值,恰好就是探险家经过这个物品买卖途径所需要付出的金钱。用dijkstra算法求出单源最短路径,从各个结点的最短路径中选出最短的那条就是答案。基本还是经典最短路问题,但做了一点小小变形主要是:
1 有结点等级限制,需要枚举等级
2 把终点的物品价值计入最短路径中去,并且找最小的最短路径输出
3 要注意是单向图,即物品替换关系是单向的
Source Code
Problem: 1062
|
|
User:
yangliuACMer
|
Memory: 300K |
|
Time: 32MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
poj 1062 昂贵的聘礼 代码 单源最短路径的Dijkstra算法
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
北大POJ1062-Expensive dowry【dijkstra】 解题报告+AC代码
pku acm 2253 Frogger 代码 单元最短路径 Dijkstra算法
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj...
Algorithm-Java Algorithms + Data Structures = Programs....最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
dijkstra 算法 需要考虑重边.........
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
用贪心算法解决POJ 1065的木棍处理问题
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
关于C++ 算法 北大网站POJ 八数码问题
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573