poj - 3225 Roadblocks(次短路）
标签：
查看更多关于poj - 3225 Roadblocks(次短路）的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did119112
poj - 3225 Roadblocks(次短路）
/* ***********************************************
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 }
阅读：26次