Dijksta算法中,如果我们采用的是邻接矩阵来存的,第一点浪费的空间比较多,第二点我们知道算法的时间复杂度在O(n*n),这样的算法可以说并不是很好,所以我们考虑优化它首先我们可以优化存储结构,采用邻接表来存储,其次我们可以用优先队列来排序大小,其时间复杂度大大降低。 需要注意的是pair是按照第一个元素的大小排序,如果相同才按照第二个,所以我们要把d[i]包装在第一个元素上。 vector实现邻接表+优先队列 (假设边一开始是字符型的,这么假设是为了加点难度) #include<iostream> …

2015年1月22日 0条评论 1点热度 阅读全文

最短路径问题 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13771    Accepted Submission(s): 4234 Problem Description 给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其…

2014年8月29日 0条评论 1点热度 阅读全文

链接:poj 1860 题意:给定n中货币,以及它们之间的税率,A货币转化为B货币的公式为 B=(V-Cab)*Rab,其中V为A的货币量, 求货币S通过若干此转换,再转换为原本的货币时是否会增加 分析:这个题就是判断是否存在正权回路,可以用bellman-ford算法,不过松弛条件相反 也可以用SPFA算法,判断经过转换后,转换为原本货币的值是否比原值大、、、 bellman-ford    0MS #include<stdio.h> #include<string.h>…

2014年7月24日 0条评论 1点热度 阅读全文

/* * About: Bellman-Ford算法 * Author: Tanky Woo * Blog: www.WuTianqi.com */ #include <iostream> using namespace std; const int maxnum = 100; const int maxint = 99999; // 边, typedef struct Edge{ int u, v; // 起点,重点 int weight; // 边的权值 }Edge; Edge edge[maxnu…

2013年4月26日 0条评论 2点热度 阅读全文

具体的我就不解释了,网上有很详细的。、 http://www.cppblog.com/MemoryGarden/archive/2008/09/04/60912.html   “ 题意 : 就是套汇的问题,汇率Rab, 增加了一个手续费  Cab 。。。。。。。每次的结果是  (本金 - 手续费) * 汇率,而且一个人拥有的钱的类型是已知的,拥有的value 钱的个数也是已知的, 问你能不能增值。 输入 : 3 2 1 20.0         …

2010年8月19日 0条评论 1点热度 阅读全文
1345672000