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 ;
}

代码搓了点