poj - 3225 Roadblocks(次短路）
时间：2021-07-01 10:21:17
帮助过：11人阅读
/* ***********************************************
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 }
poj - 3225 Roadblocks(次短路）
标签：
