次最短路径 POJ 3255 Roadblocks

http://poj.org/problem?id=3255

这道题还是有点难度

要对最短路径的算法非常的了解明晰那么做适当的修改就可以

关键之处次短的路径：设u 到 v的边权重为cost

那么到v的次短路径要么是到u的次短路径+cost；要么是到u的最短路径+cost;

那么就在dijkstra中既要保存最短路径的数组又要保存次短路径的情况

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #define MAXV 5007
 6 #define MAXE 200007
 7 #define INF 0x3f3f3f3f
 8 //向前星 125ms
 9 using namespace std;
10 typedef pair<int,int> P;
11 
12 int E, V;
13 struct Edge
14 {
15     int to, cost, next;
16     Edge () {}
17     Edge (int to, int cost, int next) : to(to), cost(cost), next(next) {}
18 }edge[MAXE];
19 int head[MAXV];
20 int num = 0;
21 void Add(int from, int to, int cost)
22 {
23     edge[num] = Edge(to, cost, head[from]);
24     head[from] = num++;
25 }
26 
27 int dijkstra()
28 {
29     int dist1[MAXV], dist2[MAXE];
30     priority_queue<P, vector<P>, greater<P> > que; 
31     fill(dist1, dist1+MAXV, INF);
32     fill(dist2, dist2+MAXV, INF);
33     dist1[1] = 0;
34     que.push(P(dist1[1], 1));
35     while (!que.empty())
36     {
37         P p = que.top();
38         que.pop();
39         int v = p.second, d = p.first;
40         if (dist2[v] < d) continue;//如果次短路径都小于d 那么就不用再继续去更新
41         int t = head[v];
42         while (t != -1)
43         {
44             Edge e = edge[t];
45             int d2 = e.cost + d;//到e.to的假设次短距离 是到v的最距离 + e.cost
46             if(d2 < dist1[e.to])//如果次短路小于最短路 交换最短路和次短路
47             {
48                 swap(dist1[e.to], d2);
49                 que.push(P(dist1[e.to], e.to));
50             }
51             if (d2 < dist2[e.to] && d2 > dist1[e.to])//如果可以更新次短路
52             {
53                 dist2[e.to] = d2;
54                 que.push(P(dist2[e.to], e.to));//这两句if 体现次短路 要么是到达其他某个顶点的最短路加上u->v这条边，要么是到u的次短路再加上u->v这条边
55             }
56             t = e.next;
57         }
58     }
59     return dist2[V];
60 }
61 
62 int main()
63 {
64     freopen("in.txt", "r", stdin);
65     scanf("%d%d", &V, &E);
66     memset(head, -1, sizeof(head));
67     memset(edge, -1, sizeof(edge));
68     for (int i = 0; i < E; i++)
69     {
70         int from, to, cost;
71         scanf("%d%d%d", &from, &to, &cost);
72         Add(from, to, cost);
73         Add(to, from, cost);
74     }
75     int ans = dijkstra();
76     //cout << ans << endl;
77     printf("%d\n", ans);
78 }

秒客网

次最短路径 POJ 3255 Roadblocks

相关文章