|
这题看起来很屌。 但是实际上走到每个点之后,速度必然是当前点和左上角点的差值的倒数。 所以,每个点到其他点的所花费的时间都是这个点自己的值决定的。 而且没可能经过一个点两次的,因为经过两次肯定是浪费时间的。 问题就变成了求最短路径。
注意: 这题的精度很莫名其妙,用C++可以AC的,G++、GCC都是WA。 不能用整数来保存时间,虽然看上去位数是够用的,但是遇到比较屌的数据就挂了。 就在这个问题上杯具了很久。
#include <stdio.h>
#include <math.h>

#ifndef _countof
#define _countof(x) (sizeof(x)/sizeof(x[0]))
#endif

#define SIZE 128

int map[SIZE][SIZE], R, C, V;
double D[SIZE][SIZE], _tbl[128], *tbl = &_tbl[64];
int queue[65536][2], head, tail;
int vis[SIZE][SIZE];

inline void push(int y, int x, double d)
  {
if (y < 0 || y >= R || x < 0 || x >= C)
return ;
if (d > D[y][x])
return ;
D[y][x] = d;
if (vis[y][x])
return ;
vis[y][x] = 1;
queue[tail][0] = y;
queue[tail][1] = x;
tail++;
tail &= _countof(queue) - 1;
}

inline void pop(int *y, int *x)
  {
*y = queue[head][0];
*x = queue[head][1];
head++;
head &= _countof(queue) - 1;
vis[*y][*x] = 0;
}

int main()
  {
int i, j;
double d;

freopen("e:\\test\\in.txt", "r", stdin);

for (i = -64; i <= 64; i++)
tbl[i] = pow(2.0, i);

scanf("%d%d%d", &V, &R, &C);
 for (i = 0; i < R; i++) {
 for (j = 0; j < C; j++) {
scanf("%d", &map[i][j]);
if (i || j)
map[i][j] -= map[0][0];
D[i][j] = 1e80;
}
}
map[0][0] = 0;

push(0, 0, 0);
 while (head != tail) {
pop(&i, &j);
d = D[i][j] + tbl[map[i][j]];
push(i + 1, j, d);
push(i - 1, j, d);
push(i, j + 1, d);
push(i, j - 1, d);
}

printf("%.2lf\n", D[R - 1][C - 1] / V);
return 0;
}

|