/*
求解单源最短路问题:Dijkstra算法(该图所有边的权值非负)
关键(贪心):
(1)找到最短距离已经确定的节点,从它出发更新与其相邻节点的最短距离;
(2)此后不再关心(1)中“最短距离已经确定的节点”。
时间复杂度(大概的分析,不准确):
“找到最短距离已经确定的节点” => O(|V|)
"从它出发更新与其相邻节点的最短距离" => 邻接矩阵:O(|V|),邻接表:O(|E|)
需要循环以上两个步骤V次,所以时间复杂度:O(V^2)
即:在|E|较小的情况下,时间主要花在了寻找最短距离已经确定的节点
考虑用二叉堆(C++ priority_queue)实现,放入二叉堆数据的操作最多有|E|次,
堆中的元素平均下来大概有|V|,故时间复杂度O(|E|log|V|)
--------------------------------------------
基础知识:
C++ priority_queue:http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
This context is similar to a heap, where elements can be inserted at any moment, and only the max
heap element can be retrieved (the one at the top in the priority queue).
缺省情况下,priority_queue利用一个大根堆完成。
引自百度百科:
二叉堆:完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最小堆。
最大堆(大根堆):父结点的键值总是大于或等于任何一个子节点的键值;
最小堆(小根堆):父结点的键值总是小于或等于任何一个子节点的键值。
完全二叉树(Complete Binary Tree)
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,
这就是完全二叉树。
--------------------------------------------
题目:
poj 1860 Currency Exchange
利用最大路径来求,改变Dijkstra算法判断条件即可。
*/
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <cstddef>
5 #include <iterator>
6 #include <algorithm>
7 #include <string>
8 #include <locale>
9 #include <cmath>
10 #include <vector>
11 #include <cstring>
12 #include <map>
13 #include <utility>
14 #include <queue>
15 #include <stack>
16 #include <set>
17 #include <functional>
18 using namespace std;
19 typedef pair<double, int> P; // first:最大货币价值 second:the number of exchange points
20 const int INF = 0x3f3f3f3f;
21 const int modPrime = 3046721;
22 const double eps = 1e-9;
23 const int MaxN = 105;
24
25 int N, M, S;
26 double V;
27 double d[MaxN];
28
29 struct Edge
30 {
31 int to;
32 double rate;
33 double commission;
34 };
35
36 vector<Edge> G[MaxN];
37
38 void Solve()
39 {
40 fill(d, d + MaxN, -1);
41 d[S] = V;
42 priority_queue<P, vector<P> > que;
43 que.push(P(d[S], S));
44 while (!que.empty())
45 {
46 P p = que.top();
47 que.pop();
48 int v = p.second;
49 if ((v == S) && (p.first - V) > eps)
50 {
51 printf("YES
");
52 return;
53 }
54 if (d[v] > p.first)
55 {
56 continue;
57 // 如果当前取出节点的货币值不是该节点的货币最大值,直接放弃这个节点货币值
58 /*
59 出现这种情况的原因是:
60 不断向二叉堆中放入更新过的数据{p.first, p.second},但是有可能同一个节点多次更新,
61 导致放入二叉堆这样一些节点:节点相同(p.second相同),节点货币值不同(p.first不同)。
62 例如假设当前二叉堆中依次放入{p.first1, p.second1},{p.first2, p.second1},{p.first3,
63 p.second1},可知 max{p.first1, p.first2, p.first3} = p.first3,此时d[p.second]已被
64 更新为p.first3,那么当从二叉堆中取出{p.first1, p.second1},{p.first2, p.second1}时,
65 直接舍弃掉即可,因为在取出前两者之前,{p.first3, p.second1}已被取出,并且已利用{p.first3,
66 p.second1}更新了其他节点的货币值(priority_queue: only the max heap element can be
67 retrieved (the one at the top in the priority queue).)。
68 */
69 }
70 for (int i = 0; i < G[v].size(); ++i)
71 {
72 Edge eg = G[v][i];
73 if (d[eg.to] < (d[v] - eg.commission)*eg.rate)
74 {
75 d[eg.to] = (d[v] - eg.commission)*eg.rate;
76 que.push(P(d[eg.to], eg.to));
77 }
78 }
79 }
80 printf("NO
");
81 }
82
83 int main()
84 {
85 #ifdef HOME
86 freopen("in", "r", stdin);
87 //freopen("out", "w", stdout);
88 #endif
89
90 scanf("%d %d %d %lf", &N, &M, &S, &V);
91 for (int i = 0; i < M; ++i)
92 {
93 int currency1, currency2;
94 scanf("%d %d", ¤cy1, ¤cy2);
95 Edge eg;
96 eg.to = currency2;
97 scanf("%lf %lf", &eg.rate, &eg.commission);
98 G[currency1].push_back(eg);
99
100 eg.to = currency1;
101 scanf("%lf %lf", &eg.rate, &eg.commission);
102 G[currency2].push_back(eg);
103 }
104
105 Solve();
106
107 #ifdef HOME
108 cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
109 _CrtDumpMemoryLeaks();
110 #endif
111 return 0;
112 }