speedcell's SPFA

版权永久属于speedcell，神代码，给跪了……yr酱V5……
这东西虽然还没有学，先收藏起来~
多谢yr酱……O(∩_∩)O哈哈~
  1 /*
  2  Author : Speedcell
  3  Update : 2013-03-24
  4 Version : soppYcell 2.1(a)
  5 */
  6 
  7 #include <algorithm>
  8 #include <iostream>
  9 #include <fstream>
 10 #include <sstream>
 11 #include <iomanip>
 12 
 13 #include <map>
 14 #include <set>
 15 #include <list>
 16 #include <stack>
 17 #include <queue>
 18 #include <deque>
 19 #include <vector>
 20 #include <string>
 21 #include <bitset>
 22 #include <memory>
 23 #include <complex>
 24 #include <numeric>
 25 
 26 #include <stdio.h>
 27 #include <stdlib.h>
 28 #include <string.h>
 29 #include <math.h>
 30 #include <time.h>
 31 #include <ctype.h>
 32 #include <locale.h>
 33 
 34 using namespace std;
 35 
 36 #pragma pack(4)
 37 
 38 #ifndef __CONSTANT__
 39 #define __CONSTANT__
 40 
 41 typedef long long LONG;
 42 
 43 const double pi = acos(-1.0);
 44 const int   inf = 0x7f7f7f7f;
 45 const LONG  INF = 0x7f7f7f7f7f7f7f7fll;
 46 
 47 const int go[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
 48 
 49 #endif // __CONSTANT__
 50 
 51 #ifndef __IO__
 52 #define __IO__
 53 
 54 inline bool RD(int    & a) {return scanf("%d",&a)!=EOF;}
 55 inline bool RD(char   & a) {return scanf("%c",&a)!=EOF;}
 56 inline bool RD(char   * a) {return scanf("%s", a)!=EOF;}
 57 inline bool RD(double & a) {return scanf("%lf",&a)!=EOF;}
 58 inline bool RD(LONG   & a) {return scanf("%I64d",&a)!=EOF;}
 59 
 60 template<class T1> inline bool
 61     IN(T1 & a) {return RD(a);}
 62 template<class T1,class T2> inline bool
 63     IN(T1 & a,T2 & b) {return RD(a)&&RD(b);}
 64 template<class T1,class T2,class T3> inline bool
 65     IN(T1 & a,T2 & b,T3 & c) {return RD(a)&&RD(b)&&RD(c);}
 66 template<class T1,class T2,class T3,class T4> inline bool
 67     IN(T1 & a,T2 & b,T3 & c,T4 & d) {return RD(a)&&RD(b)&&RD(c)&&RD(d);}
 68 template<class T1,class T2,class T3,class T4,class T5> inline bool
 69     IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e);}
 70 template<class T1,class T2,class T3,class T4,class T5,class T6> inline bool
 71     IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e,T6 & f) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e)&&RD(f);}
 72 template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline bool
 73     IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e,T6 & f,T7 & g) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e)&&RD(f)&&RD(g);}
 74 
 75 inline void PT(int    a) {printf("%d",a);}
 76 inline void PT(char   a) {printf("%c",a);}
 77 inline void PT(double a) {printf("%f",a);}
 78 inline void PT(LONG   a) {printf("%I64d",a);}
 79 inline void PT(string a) {printf("%s",a.begin());}
 80 
 81 template<class T1> inline void
 82     OT(T1 a) {PT(a);}
 83 template<class T1,class T2> inline void
 84     OT(T1 a,T2 b) {PT(a),PT(' '),PT(b);}
 85 template<class T1,class T2,class T3> inline void
 86     OT(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PT(c);}
 87 template<class T1,class T2,class T3,class T4> inline void
 88     OT(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d);}
 89 template<class T1,class T2,class T3,class T4,class T5> inline void
 90     OT(T1 a,T2 b,T3 c,T4 d,T5 e) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e);}
 91 template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
 92     OT(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f);}
 93 template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
 94     OT(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f,T7 g) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f),PT(' '),PT(g);}
 95 
 96 inline void PL(int    a) {printf("%d\n",a);}
 97 inline void PL(char   a) {printf("%c\n",a);}
 98 inline void PL(double a) {printf("%f\n",a);}
 99 inline void PL(LONG   a) {printf("%I64d\n",a);}
100 inline void PL(string a) {printf("%s\n",a.begin());}
101 
102 template<class T1> inline void
103     OL(T1 a) {PL(a);}
104 template<class T1,class T2> inline void
105     OL(T1 a,T2 b) {PT(a),PT(' '),PL(b);}
106 template<class T1,class T2,class T3> inline void
107     OL(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PL(c);}
108 template<class T1,class T2,class T3,class T4> inline void
109     OL(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PL(d);}
110 template<class T1,class T2,class T3,class T4,class T5> inline void
111     OL(T1 a,T2 b,T3 c,T4 d,T5 e) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PL(e);}
112 template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
113     OL(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PL(f);}
114 template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
115     OL(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f,T7 g) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f),PT(' '),PL(g);}
116 
117 #endif // __IO__
118 
119 #ifndef __MACRO__
120 #define __MACRO__
121 
122 #define ML(times) int tcase; IN(tcase); FOR(times,1,tcase)
123 
124 #define FOR(i,a,b) for(int i=int(a),_##i=int(b);i<=_##i;i++)
125 #define DWN(i,b,a) for(int i=int(b),_##i=int(a);_##i<=i;i--)
126 #define ECH(i,u,pre,next) for(int i=int(pre[u]);i!=-1;i=int(next[i]))
127 
128 #define MEM(a,v) memset(a,v,sizeof(a))
129 #define CLR(a,v) FOR(_i##a,0,sizeof(a)/sizeof(a[0])-1) a[_i##a]=v
130 
131 #define LOOP(a,n)                                               \
132     FOR(_i##a,0,(n)-1)                                          \
133         cout<<a[_i##a]<<(_i##a!=n-1?' ':'\n')
134 #define LOOP2(a,n,m)                                            \
135     FOR(_i##a,0,(n)-1) FOR(_j##a,0,(m)-1)                       \
136         cout<<a[_i##a][_j##a]<<(_j##a!=m-1?' ':'\n')
137 #define LOOPG(G,n,pre,next)                                     \
138     FOR(_i##a,0,(n)-1) ECH(_j##a,_i##a,pre,next)                \
139         cout<<_i##a<<" "<<G[_j##a].v<<" "<<G[_j##a].w<<endl
140 
141 #endif // __MACRO__
142 
143 #ifndef __BIT__
144 #define __BIT__
145 
146 template<class T> inline T lb(T i) {return i&-i;}
147 template<class T> inline T lc(T i) {return i<<T(1);}
148 template<class T> inline T rc(T i) {return i<<T(1)|T(1);}
149 template<class T> inline T at(T a,int i) {return a& (T(1)<<i);}
150 template<class T> inline T nt(T a,int i) {return a^ (T(1)<<i);}
151 template<class T> inline T s1(T a,int i) {return a| (T(1)<<i);}
152 template<class T> inline T s0(T a,int i) {return a&~(T(1)<<i);}
153 
154 #endif // __BIT__
155 
156 #ifndef __DOUBLE__
157 #define __DOUBLE__
158 
159 const double eps = 1e-8;
160 
161 inline int cmp(double a) {return fabs(a-0)<eps?0:((a-0)>eps?+1:-1);}
162 inline int cmp(double a,double b) {return fabs(a-b)<eps?0:((a-b)>eps?+1:-1);}
163 
164 inline double fmax(double a,double b) {return cmp(a,b)>0?a:b;}
165 inline double fmin(double a,double b) {return cmp(a,b)<0?a:b;}
166 
167 #endif // __DOUBLE__
168 
169 const int MAXV = 12000;
170 const int MAXE = 24000;
171 
172 struct node
173 {
174     int v,w;
175 }G[MAXE];
176 int _index,pre[MAXV],next[MAXE];
177 
178 void clear(void)
179 {
180     _index=0;
181     MEM(pre,-1);
182 }
183 void add(int u,int v,int w)
184 {
185     G[_index].v=v;
186     G[_index].w=w;
187     next[_index]=pre[u];
188     pre[u]=_index++;
189 }
190 
191 class HEAP
192 {
193 private:
194     int use,val[MAXV],lab[MAXV],heap[MAXV];
195 
196     int sel(int i,int j)
197     {
198         return val[heap[i]]<val[heap[j]]?i:j;
199     }
200     void change(int i,int j)
201     {
202         swap(heap[i],heap[j]);
203         swap(lab[heap[i]],lab[heap[j]]);
204     }
205 public:
206     int operator [] (int i)
207     {
208         return val[i];
209     }
210 
211     bool empty(void)
212     {
213         return use==0;
214     }
215 
216     void clear(void)
217     {
218         use=0;
219         MEM(val,inf);
220         MEM(lab,inf);
221     }
222 
223     void update(int u,int w)
224     {
225         if(val[u]>w)
226         {
227             val[u]=w;
228             if(lab[u]==inf) heap[lab[u]=++use]=u;
229 
230             for(int i=lab[u];i/2>=1;i=i/2)
231             {
232                 if(sel(i,i/2)==i/2) break;
233                 else change(i,i/2);
234             }
235         }
236     }
237 
238     int peek(void)
239     {
240         change(1,use);
241         lab[heap[use--]]=inf;
242 
243         for(int i=1;lc(i)<=use;)
244         {
245             if(lc(i)==use)
246             {
247                 if(sel(i,lc(i))==i) break;
248                 else i=lc(i);
249             }
250             else
251             {
252                 if(sel(i,sel(lc(i),rc(i)))==i) break;
253                 else i=sel(i,sel(lc(i),rc(i)));
254             }
255             change(i,i/2);
256         }
257         return heap[use+1];
258     }
259 }dis;
260 
261 int SPFA(int src,int des)
262 {
263     dis.clear();
264     dis.update(src,0);
265 
266     while(!dis.empty())
267     {
268         int u=dis.peek();
269         for(int i=pre[u];i!=-1;i=next[i])
270         {
271             dis.update(G[i].v,dis[u]+G[i].w);
272         }
273     }
274 
275     return dis[des];
276 }
277 
278 int n,m,u,v,w;
279 
280 int main()
281 {
282     while(cin>>n>>m)
283     {
284         clear();
285         while(m--)
286         {
287             cin>>u>>v>>w;
288             add(u,v,w);
289         }
290         cin>>u>>v;
291         cout<<SPFA(u,v)<<endl;
292     }
293     return 0;
294 }
好腻害……