题目：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 ;
}
网友评论