HDU ACM 3790 最短路径问题

最短路径问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8219 Accepted Submission(s): 2456

[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=3790

【解题思路】Dijk + heap【单元最短路】既然有两考虑的因素，而且分优先，那么优先队列排列比较的时候就先考虑路径长度，在路径长度相等的前提下在考虑花费的大小，即路径小花费少的先出，在细节进队的时候也是这样考虑，过一遍Dijk最后输出需要的值

【PS】刚学最短路，一开始没考虑清楚，不知该如何下手，但知道问题出在对Dij算法的掌握程度上，如果像之前的刚学的最短路情形（只有一个考虑的元素），估计也会敲出来，后来自己实现了这题的代码时，发现思路也是一样的，单个因素的最短路中，进队的时候判断能否进队用的是小于关系运算符，如果也存在多条最短路的时候，因为小于关系运算的缘故，这时起始点到这个点的相同长度的最短路径不会进队列（因为已有进入队列的相同长度的路径），但如果还有考虑的因素时，这是就不一样了，像这题，在路径长度的判断上就要改用小于等于关系运算符，因为在路径长度相等的时候，其还有次要考虑因素，这时，次要考虑因素的比较上就需要用到小于关系运算符。

一开始考虑错误的方向是将从源点到终点整条最短路径与其最小花费进行权衡，没有考虑到：在优先队列中，一出队列，如果之前没有被访问，那么就意味着锁定了这个点的最短路径和最小花费，再次困扰的是此时的点是如何如何影响到后续点的路径和花费，所以不敢确定了是否该这样进行。最后想到：假设其（当前出队列的点）只有一条最短路径，那么就可以放心的往下进行，因为这种情况回到了单个考虑因素的情况嘛，如果有多条最短路径呢？那么其肯定都在队列当中，你现在就要做的就是在其中找到一条最优的（根据次要因素判断）出队列才行，根据自己的理解，感觉还是不太够成熟 ^_^

一直不敢对Dij等各种算法用得理直气壮，该学的是思想，这是最重要的，别拿着别人的算法用得好像是自家的似的。

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int NV = 1002;
 8 const int NE = 100002;
 9 const int INF = 1<<30;
10 int ne, nv, term, tern, tot;
11 bool vis[NV];
12 int dist[NV];
13 int purse[NV];
14 struct Edge{
15     int v, cost, money, next;
16     Edge(){}
17     Edge(int a, int c, int m){v = a, cost = c, money = m;}
18     Edge(int a, int c, int m, int d){v = a, cost = c, money = m, next = d;}
19     bool operator < (const Edge& x) const
20     {
21         if(cost != x.cost) return cost > x.cost;
22         else return money > x.money; 
23     }
24 }edge[NE];
25 int eh[NV];
26 
27 void Dij(int s)
28 {
29     for(int i = 1; i <= nv; ++i) purse[i] = dist[i] = i == s ? 0 : INF;
30     priority_queue<Edge> que;
31     que.push(Edge(s, 0, 0));
32     while(!que.empty())
33     {
34         Edge tmp = que.top();
35         int u = tmp.v;
36         que.pop();
37         if(vis[u]) continue;
38         vis[u] = true;
39         for(int i = eh[u]; i != -1; i = edge[i].next)
40         {
41             int v = edge[i].v;
42             if(!vis[v] && dist[v] >= edge[i].cost + dist[u])
43             {
44                 if(dist[v] > edge[i].cost + dist[u] || 
45                 (dist[v] == edge[i].cost + dist[u] && purse[v] > edge[i].money + purse[u]))
46                 {
47                     dist[v] = edge[i].cost + dist[u];
48                     purse[v] = edge[i].money + purse[u];
49                     que.push(Edge(v, dist[v], purse[v]));
50                 }
51 
52             }
53         }
54     }
55     return;
56 }
57 
58 void addedge(int u, int v, int cost, int money)
59 {
60     Edge e = Edge(v, cost, money, eh[u]);
61     edge[tot] = e;
62     eh[u] = tot++;
63     return;
64 }
65 
66 int main()
67 {
68     #ifndef ONLINE_JUDGE
69     freopen("input.txt", "r", stdin);
70     #endif
71     while(scanf("%d%d", &nv, &ne) != EOF && nv+ne)
72     {
73         memset(eh, -1, sizeof(eh));
74         memset(vis, false, sizeof(vis));
75         term = tern = tot = 0;
76         int u, v, cost, money;
77         for(int i = 0; i < ne; ++i)
78         {
79             scanf("%d%d%d%d", &u, &v, &cost, &money);
80             addedge(u, v, cost, money);
81             addedge(v, u, cost, money);
82         }
83         int s, t;
84         scanf("%d%d", &s, &t);
85         Dij(s);
86         printf("%d %d
", dist[t], purse[t]);
87     }
88     return 0;
89 }