dijkstra堆优化及set用法内容摘要：
行有 ２ 种形式： “ B S” ：表示得到价值为 S的图片 “ G” ：表示要给出当时价值最小的图片 n = 0表示输入结束． toj2196Nuanran39。 s Idol II 输出：按照“ G”的顺序输出所有给出图片的价值 开始时 nuanran没有图片 样例输入： 8 B 20 B 10 G B 9 G B 100 B 25 G 0 toj2196Nuanran39。 s Idol II 样例输出： 10 9 20 分析，这道题的实质就是维护一个集合，支持 ２ 个操作，插入一个元素，删除最小元，这个可以用堆来实现，不过如果用multiset来实现，代码会很轻松的实现。 大家可以试试 Dijkstra算法的优化 复习一下算法： s表示起点， t表示终点， path数组表示所有点到 s的距离 ,集合 S表示已经找到最短路的点集． 1， path[s] = 0, 其他 path为正无穷， S为空集 2，找到不在 S中 path值最小的点，用它更新周围点的 path值，然后把它加到 S中 3，如果 t不在 S中，重复 2，否则退出 Dijkstra算法的优化 其中第 2步中找到最小的 path值的点可以用 set来实现 : include include include set define MAX 1000000 using namespace std。 typedef struct nn { int v, w。 struct nn *next。 } node。 Dijkstra算法的优化 node pool[MAX], *pp, *adj[MAX]。 //申请节点前一定要 pp = pool int n, path[MAX]。 //记录最短路 bool vis[MAX]。 struct cmp { bool operator()( const int amp。 a, const int amp。 b ) const { return path[a] path[b] || ( path[a] == path[b] amp。 amp。 a b )。 } }。 //这里用 p。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。