poj3037 解题报告

这道题也是我拿来测板子的

题意：给定一个r*c(r<=100,c<=100)的矩阵，每个元素表示该点高度，给定初始速度v，当从一点移动到另一点后，速度变为原先的2^(该点高度-移动到的点的高度)，花费时间是1/原先高度，求从1,1到r,c的最短时间

题解：可以推出，每个点速度是一样的，这样就直接最短路了

#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <cmath>using namespace std ;const int MAXN = 105 ;const int MAXM = MAXN * MAXN * 20 ;double INF = 9999999999.0 ;double EPS = 0.000000001  ;struct type{    int  end , next ;    double length ;} ;type  edge[MAXM] ;int   val[MAXN][MAXN]     ;int   head[MAXN*MAXN]     ;int   cnt[MAXN*MAXN]      ;int   V , R , C , Count   ;bool  vis[MAXN*MAXN]      ;double  dis[MAXN*MAXN]    ;double  speed[MAXN][MAXN] ;int  dx[4] = { 0 , 0 , 1 , -1 } ;int  dy[4] = { 1 , -1 , 0 , 0 } ;void  addedge( int start , int end , double length ){    edge[Count].end    = end         ;    edge[Count].length = length      ;    edge[Count].next   = head[start] ;    head[start]        = Count ++    ;}double SPFA( int start , int n ){int  i ;memset( cnt , 0 , sizeof( cnt ) ) ;memset( vis , 0 , sizeof( vis ) ) ;for( i = 1 ; i <= n ; i ++ ) dis[i] = INF ;dis[start] = 0 ;queue < int > q ;q.push( start ) ; vis[start] = true ; ++ cnt[start] ;while( ! q.empty() ){int  u , v ;u = q.front() ;  q.pop() ;   vis[u] = false ;for( i = head[u] ; i != -1 ; i = edge[i].next ) {v = edge[i].end ;if( dis[v] > dis[u] + edge[i].length + EPS  ){dis[v] = dis[u] + edge[i].length ;if( !vis[v] ){q.push( v ) ;vis[v] = true ;if( ++cnt[v] > n ) return -1 ;}}}}return 0 ;}int  main(){    int  i , j , k ;    memset( head  , -1 , sizeof( head  ) ) ;    memset( vis   ,  0 , sizeof( vis   ) ) ;    memset( speed , -1 , sizeof( speed ) ) ;    Count = 0 ;    scanf( "%d%d%d" , & V , & R , & C ) ;    for( i = 0 ; i < R ; i ++ )        for( j = 0 ; j < C ; j ++ )            scanf( "%d" , & val[i][j] ) ;    speed[0][0] = V ;    for( i = 1 ; i < C ; i ++ )        speed[0][i] = speed[0][i-1] * pow( 2 , double ( val[0][i-1] - val[0][i] ) )  ;    for( i = 1 ; i < R ; i ++ )        for( j = 0 ; j < C ; j ++ )            speed[i][j] = speed[i-1][j] * pow( 2 , double ( val[i-1][j] - val[i][j] ) ) ;    for( i = 0 ; i < R ; i ++ )        for( j = 0 ; j < C ; j ++ )            for( k = 0 ; k < 4 ; k ++ )            {                int tmpx = i + dx[k] ;                int tmpy = j + dy[k] ;                if( tmpx >= 0 && tmpx < R && tmpy >= 0 && tmpy < C )                    addedge( ( i * C + j ) , ( tmpx * C + tmpy ) , 1.0 / speed[i][j] ) ;            }    SPFA( 0 , R * C ) ;    printf( "%.2f\n" , dis[R * C - 1] ) ;    return 0 ;}