poj - 3225 Roadblocks(次短路）

浏览数：21 / 时间：2015年06月12日

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

bessie 有时会去拜访她的朋友，但是她不想走最快回家的那条路，而是想走一条比最短的路长的次短路。

城镇由R条双向路组成，有N个路口。标号为1到N,问1号路口到N号路口的次短路长度是多少？次短路是

比最短路长度长的次短的路径。同一条边可以经过多次。

到某个顶点v的次短路要么帅到其他顶点u的最短路在加上u-v的边，要么是到u的次短路再加上u-v的边，

因此所需要求的就是到所有顶点的最短路和次短路，因此，对于每个顶点，我们记录的不仅仅是最短距离，

还有次短的距离，接下去只要用dijkstra算法相同的做法，不断更新这两个距离就能求出次短路了。

 1 /* ***********************************************
 2 Author        : zch
 3 Created Time  :2015/5/13 8:16:45
 4 File Name     :a.cpp
 5  ************************************************ */
 6 
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <cmath>
17 #include <cstdlib>
18 #include <ctime>
19 using namespace std;
20 const int maxn = 5010;
21 const int INF = 1000000000;
22 
23 int N, R;
24 struct edge {
25     int to,cost;
26     edge() {}
27     edge(int x,int y) {
28         to=x;
29         cost=y;
30     }
31 };
32 typedef pair<int,int>P;
33 vector<edge>G[maxn];
34 int dist[maxn];
35 int dist2[maxn];
36 
37 void dijkstra(int s) {
38     priority_queue<P,vector<P>,greater<P> >que;
39     for(int i=0;i<=N;i++) dist[i]=INF;
40     for(int i=0;i<=N;i++) dist2[i]=INF;
41     dist[s]=0;
42     que.push(P(0,s));
43 
44     while(!que.empty()) {
45         P p=que.top(); que.pop();
46         int v=p.second, d=p.first;
47         if(dist2[v]<d) continue;  //v的次短距离比d还小
48         for(int i=0;i<G[v].size();++i) {
49             edge e=G[v][i];
50             //cout<<e.to<<endl;
51             int d2=d+e.cost;
52             if(dist[e.to]>d2) {  //更新 最短距离
53                 swap(dist[e.to],d2);
54                 que.push(P(dist[e.to],e.to));
55             }
56             if(dist2[e.to]>d2&&dist[e.to]<d2) {  //更新次短距离
57                 dist2[e.to]=d2;
58                 //cout<<d2<<endl;
59                 que.push(P(dist2[e.to],e.to));
60             }
61         }
62     }
63     printf("%d\n",dist2[N]);
64 }
65 int main()
66 {
67     //freopen("a.txt","r",stdin);
68     //freopen("b.txt","w",stdout);
69     int a,b,c;
70     scanf("%d%d",&N,&R);
71     for(int i=0;i<R;++i) {
72         scanf("%d%d%d",&a,&b,&c);
73         G[a].push_back(edge(b,c));
74         G[b].push_back(edge(a,c));
75     }
76     dijkstra(1);
77     return 0;
78 }