BZOJ-1415: [Noi2005]聪聪和可可（最短路+动态

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

最短路预处理，然后DP求解即可。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
#include <vector>
 
using namespace std ;
 
#define AddEdge( s , t ) e[ s ].pb( t ) , e[ t ].pb( s )
#define maxn 1010
#define pb push_back
#define pf push_front
#define inf 0x7fffffff
#define travel( s ) for ( vector < int > :: iterator p = e[ s ].begin(  ) ; p != e[ s ].end(  ) ; ++ p )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; ) 
 
vector < int > e[ maxn ] ;
int n , m , st , to , next[ maxn ][ maxn ] , d[ maxn ] ;
 
int dist[ maxn ] ;
deque < int > q ;
bool f[ maxn ] ;
 
void spfa( int S ) {
        memset( f , false , sizeof( f ) ) , q.clear(  ) ;
        rep( i , n ) dist[ i ] = inf ;
        dist[ S ] = 0 , f[ S ] = true , q.pf( S ) ;
        while ( ! q.empty(  ) ) {
               int v = q.front(  ) ; q.pop_front(  ) , f[ v ] = false ;
               travel( v ) if ( dist[ *p ] > dist[ v ] + 1 ) {
                       dist[ *p ] = dist[ v ] + 1 ;
                       if ( ! f[ *p ] ) {
                               f[ *p ] = true ;
                              if ( ! q.empty(  ) && dist[ *p ] < dist[ q.front(  ) ] ) q.pf( *p ) ; else q.pb( *p ) ;
                       }
               }
        }
}
 
double dp[ maxn ][ maxn ] ;
bool flag[ maxn ][ maxn ] ;
 
double Dp( int v , int u ) {
        if ( flag[ v ][ u ] ) return dp[ v ][ u ] ;
        if ( v == u ) {
               dp[ v ][ u ] = 0 , flag[ v ][ u ] = true ;
               return dp[ v ][ u ] ;
        }
        int k = next[ v ][ u ] ;
        if ( k != u ) k = next[ k ][ u ] ;
        dp[ v ][ u ] = 1 ;
        if ( k != u ) {
               travel( u ) dp[ v ][ u ] += Dp( k , *p ) / double( d[ u ] + 1 ) ;
               dp[ v ][ u ] += Dp( k , u ) / double( d[ u ] + 1 ) ;
        }
        flag[ v ][ u ] = true ;
        return dp[ v ][ u ] ;
}
 
int main(  ) {
        scanf( "%d%d" , &n , &m ) ; 
        scanf( "%d%d" , &st , &to ) ;
        memset( d , 0 , sizeof( d ) ) ;
        while ( m -- ) {
               int s , t ; scanf( "%d%d" , &s , &t ) ; AddEdge( s , t ) ;
               ++ d[ s ] , ++ d[ t ] ;
        }
        memset( next , 0 , sizeof( next ) ) ;
        rep( i , n ) {
               spfa( i ) ;
               rep( j , n ) travel( j ) if ( ! next[ j ][ i ] || dist[ *p ] < dist[ next[ j ][ i ] ] || ( dist[ *p ] == dist[ next[ j ][ i ] ] && *p < next[ j ][ i ] ) ) {
                       next[ j ][ i ] = *p ;
               }
        }
        memset( flag , false , sizeof( flag ) ) ;
        printf( "%.3f\n" , Dp( st , to ) ) ;
        return 0 ;
}