Roadblocks -次短路

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <ctype.h>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 const int MAXN=5010;
11 const int INF=1e9;
12 
13 int n,m;
14 
15 int dis[MAXN],dis2[MAXN];
16 
17 typedef pair<int,int> P;
18 
19 struct edge {
20     int to;
21     int val;
22 };
23 vector<edge> G[MAXN];
24 
25 inline void read(int&x) {
26     int f=1;register char c=getchar();
27     for(x=0;!isdigit(c);c==‘-‘&&(f=-1),c=getchar());
28     for(;isdigit(c);x=x*10+c-48,c=getchar());
29     x=x*f;
30 }
31 
32 inline void SPFA() {
33     priority_queue<P,vector<P>,greater<P> >Q;
34     for(int i=0;i<=n;++i) dis[i]=dis2[i]=INF;
35     Q.push(P(1,0));
36     dis[1]=0;
37     while(!Q.empty()) {
38         P u=Q.top();
39         Q.pop();
40         int v=u.first,V=u.second;
41         if(dis2[v]<V) continue;
42         for(int i=0;i<G[v].size();++i) {
43             edge e=G[v][i];
44             int d=V+e.val;
45             if(dis[e.to]>d) {
46                 swap(dis[e.to],d);
47                 Q.push(P(e.to,dis[e.to]));
48             }
49             if(dis2[e.to]>d&&d>dis[e.to]) {
50                 dis2[e.to]=d;
51                 Q.push(P(e.to,dis2[e.to]));
52             }
53         }
54     }
55     return;
56 }
57 
58 int hh() {
59 //    freopen("1.in","r",stdin);
60 //    freopen("2.out","w",stdout);
61     read(n);read(m);
62     for(int x;m--;) {
63         edge p;
64         read(x);read(p.to);read(p.val);
65 //        --x,--p.to;
66         G[x].push_back(p);
67         swap(p.to,x);
68         G[x].push_back(p);
69     }
70     SPFA();
71     printf("%d\n",dis2[n]);
72     return 0;
73 }
74 
75 int sb=hh();
76 int main() {;}

Roadblocks -次短路

标签：sample   pre   first   wap   次短路   algorithm   too   ret   count