speedcell's SPFA

版权永久属于speedcell，神代码，给跪了……yr酱V5…… 这东西虽然还没有学，先收藏起来~ 多谢yr酱……O(∩_∩)O哈哈~

/*
 Author : Speedcell
 Update : 2013-03-24
Version : soppYcell 2.1(a)
*/

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <memory>
#include <complex>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

#pragma pack(4)

#ifndef __CONSTANT__
#define __CONSTANT__

typedef long long LONG;

const double pi = acos(-1.0);
const int   inf = 0x7f7f7f7f;
const LONG  INF = 0x7f7f7f7f7f7f7f7fll;

const int go[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

#endif // __CONSTANT__

#ifndef __IO__
#define __IO__

inline bool RD(int    & a) {return scanf("%d",&a)!=EOF;}
inline bool RD(char   & a) {return scanf("%c",&a)!=EOF;}
inline bool RD(char   * a) {return scanf("%s", a)!=EOF;}
inline bool RD(double & a) {return scanf("%lf",&a)!=EOF;}
inline bool RD(LONG   & a) {return scanf("%I64d",&a)!=EOF;}

template<class T1> inline bool
    IN(T1 & a) {return RD(a);}
template<class T1,class T2> inline bool
    IN(T1 & a,T2 & b) {return RD(a)&&RD(b);}
template<class T1,class T2,class T3> inline bool
    IN(T1 & a,T2 & b,T3 & c) {return RD(a)&&RD(b)&&RD(c);}
template<class T1,class T2,class T3,class T4> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d) {return RD(a)&&RD(b)&&RD(c)&&RD(d);}
template<class T1,class T2,class T3,class T4,class T5> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e);}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline bool
    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);}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline bool
    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);}

inline void PT(int    a) {printf("%d",a);}
inline void PT(char   a) {printf("%c",a);}
inline void PT(double a) {printf("%f",a);}
inline void PT(LONG   a) {printf("%I64d",a);}
inline void PT(string a) {printf("%s",a.begin());}

template<class T1> inline void
    OT(T1 a) {PT(a);}
template<class T1,class T2> inline void
    OT(T1 a,T2 b) {PT(a),PT(' '),PT(b);}
template<class T1,class T2,class T3> inline void
    OT(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PT(c);}
template<class T1,class T2,class T3,class T4> inline void
    OT(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d);}
template<class T1,class T2,class T3,class T4,class T5> inline void
    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);}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
    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);}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
    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);}

inline void PL(int    a) {printf("%d\n",a);}
inline void PL(char   a) {printf("%c\n",a);}
inline void PL(double a) {printf("%f\n",a);}
inline void PL(LONG   a) {printf("%I64d\n",a);}
inline void PL(string a) {printf("%s\n",a.begin());}

template<class T1> inline void
    OL(T1 a) {PL(a);}
template<class T1,class T2> inline void
    OL(T1 a,T2 b) {PT(a),PT(' '),PL(b);}
template<class T1,class T2,class T3> inline void
    OL(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PL(c);}
template<class T1,class T2,class T3,class T4> inline void
    OL(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PL(d);}
template<class T1,class T2,class T3,class T4,class T5> inline void
    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);}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
    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);}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
    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);}

#endif // __IO__

#ifndef __MACRO__
#define __MACRO__

#define ML(times) int tcase; IN(tcase); FOR(times,1,tcase)

#define FOR(i,a,b) for(int i=int(a),_##i=int(b);i<=_##i;i++)
#define DWN(i,b,a) for(int i=int(b),_##i=int(a);_##i<=i;i--)
#define ECH(i,u,pre,next) for(int i=int(pre[u]);i!=-1;i=int(next[i]))

#define MEM(a,v) memset(a,v,sizeof(a))
#define CLR(a,v) FOR(_i##a,0,sizeof(a)/sizeof(a[0])-1) a[_i##a]=v

#define LOOP(a,n)                                               \
    FOR(_i##a,0,(n)-1)                                          \
        cout<<a[_i##a]<<(_i##a!=n-1?' ':'\n')
#define LOOP2(a,n,m)                                            \
    FOR(_i##a,0,(n)-1) FOR(_j##a,0,(m)-1)                       \
        cout<<a[_i##a][_j##a]<<(_j##a!=m-1?' ':'\n')
#define LOOPG(G,n,pre,next)                                     \
    FOR(_i##a,0,(n)-1) ECH(_j##a,_i##a,pre,next)                \
        cout<<_i##a<<" "<<G[_j##a].v<<" "<<G[_j##a].w<<endl

#endif // __MACRO__

#ifndef __BIT__
#define __BIT__

template<class T> inline T lb(T i) {return i&-i;}
template<class T> inline T lc(T i) {return i<<T(1);}
template<class T> inline T rc(T i) {return i<<T(1)|T(1);}
template<class T> inline T at(T a,int i) {return a& (T(1)<<i);}
template<class T> inline T nt(T a,int i) {return a^ (T(1)<<i);}
template<class T> inline T s1(T a,int i) {return a| (T(1)<<i);}
template<class T> inline T s0(T a,int i) {return a&~(T(1)<<i);}

#endif // __BIT__

#ifndef __DOUBLE__
#define __DOUBLE__

const double eps = 1e-8;

inline int cmp(double a) {return fabs(a-0)<eps?0:((a-0)>eps?+1:-1);}
inline int cmp(double a,double b) {return fabs(a-b)<eps?0:((a-b)>eps?+1:-1);}

inline double fmax(double a,double b) {return cmp(a,b)>0?a:b;}
inline double fmin(double a,double b) {return cmp(a,b)<0?a:b;}

#endif // __DOUBLE__

const int MAXV = 12000;
const int MAXE = 24000;

struct node
{
    int v,w;
}G[MAXE];
int _index,pre[MAXV],next[MAXE];

void clear(void)
{
    _index=0;
    MEM(pre,-1);
}
void add(int u,int v,int w)
{
    G[_index].v=v;
    G[_index].w=w;
    next[_index]=pre[u];
    pre[u]=_index++;
}

class HEAP
{
private:
    int use,val[MAXV],lab[MAXV],heap[MAXV];

    int sel(int i,int j)
    {
        return val[heap[i]]<val[heap[j]]?i:j;
    }
    void change(int i,int j)
    {
        swap(heap[i],heap[j]);
        swap(lab[heap[i]],lab[heap[j]]);
    }
public:
    int operator [] (int i)
    {
        return val[i];
    }

    bool empty(void)
    {
        return use==0;
    }

    void clear(void)
    {
        use=0;
        MEM(val,inf);
        MEM(lab,inf);
    }

    void update(int u,int w)
    {
        if(val[u]>w)
        {
            val[u]=w;
            if(lab[u]==inf) heap[lab[u]=++use]=u;

            for(int i=lab[u];i/2>=1;i=i/2)
            {
                if(sel(i,i/2)==i/2) break;
                else change(i,i/2);
            }
        }
    }

    int peek(void)
    {
        change(1,use);
        lab[heap[use--]]=inf;

        for(int i=1;lc(i)<=use;)
        {
            if(lc(i)==use)
            {
                if(sel(i,lc(i))==i) break;
                else i=lc(i);
            }
            else
            {
                if(sel(i,sel(lc(i),rc(i)))==i) break;
                else i=sel(i,sel(lc(i),rc(i)));
            }
            change(i,i/2);
        }
        return heap[use+1];
    }
}dis;

int SPFA(int src,int des)
{
    dis.clear();
    dis.update(src,0);

    while(!dis.empty())
    {
        int u=dis.peek();
        for(int i=pre[u];i!=-1;i=next[i])
        {
            dis.update(G[i].v,dis[u]+G[i].w);
        }
    }

    return dis[des];
}

int n,m,u,v,w;

int main()
{
    while(cin>>n>>m)
    {
        clear();
        while(m--)
        {
            cin>>u>>v>>w;
            add(u,v,w);
        }
        cin>>u>>v;
        cout<<SPFA(u,v)<<endl;
    }
    return 0;
}

好腻害……