BZOJ-2750: [HAOI2012]Road（SPFA+拓

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2750

太久没刷水题的话对身体不好啊~~~~~_{于是乎我又来刷水题啦}

嘛嘛，这题思路挺清晰的，先枚举源点，然后最短路n次，每次都正向和反向在最短路树上拓扑DP统计路径条数，然后某边如果在最短路上就乘起来，最后累加就好啦~

代码（没用DJ用了SPFA没想到还挺快的。。。）：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <deque>

 

using namespace std ;

 

#define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

 

#define pf push_front

#define pb push_back

 

typedef long long ll ;

 

const int maxn = 1510 , maxm = 5010 , inf = 0x7ffffff ;

const ll mod = 1000000007 ;

 

inline ll add( ll val , ll del ) {

    return ( val + del ) % mod ;

}

 

inline ll mul( ll x , ll y ) {

    return ( x * y ) % mod ;

}

 

struct graph {

     

    struct edge {

        int t , d ;

        edge *next ;

    } E[ maxm ] ;

     

    edge *head[ maxn ] , *pt ;

     

    inline void addedge( int s , int t , int d ) {

        pt -> t = t , pt -> d = d , pt -> next = head[ s ] ;

        head[ s ] = pt ++ ;

    }

     

    deque < int > q ;

    bool used[ maxn ] ;

    int dist[ maxn ] , V ;

     

    inline void Init( int _V ) {

        V = _V , pt = E ;

        rep( i , V ) head[ i ] = NULL ;

    }

     

    inline void spfa( int S ) {

        rep( i , V ) {

            used[ i ] = false , dist[ i ] = inf ;

        }

        q.clear(  ) ;

        dist[ S ] = 0 , used[ S ] = true , q.pb( S ) ;

        int now , cost ;

        while ( ! q.empty(  ) ) {

            now = q.front(  ) ; q.pop_front(  ) , used[ now ] = false ;

            travel( now ) if ( ( cost = dist[ now ] + p -> d ) < dist[ p -> t ] ) {

                dist[ p -> t ] = cost ;

                if ( ! used[ p -> t ] ) {

                    used[ p -> t ] = true ;

                    if ( q.empty(  ) ) q.pb( p -> t ) ; else if ( cost < dist[ q.front(  ) ] ) q.pf( p -> t ) ; else q.pb( p -> t ) ;

                }

            }

        }

    }

     

    ll f[ maxn ] ;

    int d[ maxn ] ;

     

    inline void dp(  ) {

        rep( i , V ) d[ i ] = 0 ;

        q.clear(  ) ;

        rep( i , V ) travel( i ) ++ d[ p -> t ] ;

        rep( i , V ) if ( ! d[ i ] ) q.pb( i ) ;

        int now ;

        while ( ! q.empty(  ) ) {

            now = q.front(  ) ; q.pop_front(  ) ;

            travel( now ) {

                f[ p -> t ] = add( f[ p -> t ] , f[ now ] ) ;

                if ( ! ( -- d[ p -> t ] ) ) q.pb( p -> t ) ;

            }

        }

    }

      

} g , T , IT ;

 

int n , m , e[ maxm ][ 3 ] ;

ll ans[ maxm ] ;

 

int main(  ) {

    scanf( "%d%d" , &n , &m ) ;

    g.Init( n ) ;

    int s , t , d ;

    rep( i , m ) {

        scanf( "%d%d%d" , &e[ i ][ 0 ] , &e[ i ][ 1 ] , &e[ i ][ 2 ] ) ;

        g.addedge( e[ i ][ 0 ] , e[ i ][ 1 ] , e[ i ][ 2 ] ) ;

    }

    rep( i , n ) {

        g.spfa( i ) , T.Init( n ) , IT.Init( n ) ;

        rep( j , m ) {

            s = e[ j ][ 0 ] , t = e[ j ][ 1 ] , d = e[ j ][ 2 ] ;

            if ( g.dist[ t ] == g.dist[ s ] + d ) {

                T.addedge( s , t , 0 ) , IT.addedge( t , s , 0 ) ;

            }

        }

        rep( j , n ) {

            T.f[ j ] = 0 , IT.f[ j ] = 1 ;

        }

        T.f[ i ] = 1 ;

        T.dp(  ) , IT.dp(  ) ;

        rep( j , m ) {

            s = e[ j ][ 0 ] , t = e[ j ][ 1 ] , d = e[ j ][ 2 ] ;

            if ( g.dist[ t ] == g.dist[ s ] + d ) {

                ans[ j ] = add( ans[ j ] , mul( T.f[ s ] , IT.f[ t ] ) ) ;

            }

        }

    }

    rep( i , m ) printf( "%lld\n" , ans[ i ] ) ;

    return 0 ;

}