首先到每个点的速度实际上是一个定值,就是v0*2^(起点与当前点高度差)
所以当前点i到任意一个相邻点的时间都是一个定值,
不难想到构图最短路径
const dx:array[..] of integer=(-,,,);
dy:array[..] of integer=(,,-,);
inf=; type link=^node;
node=record
po:longint;
len:double;
next:link;
end;
point=record
num:longint;
dis:double;
end; var num,a:array[..,..] of longint;
d:array[..] of double;
w:array[..] of link;
heap:array[..] of point;
where:array[..] of longint;
t,i,j,n,m,k,x,y:longint;
v,vn,mid:double;
p:link; procedure add(x,y:longint;c:double);
var p:link;
begin
new(p);
p^.po:=y;
p^.len:=c;
p^.next:=w[x];
w[x]:=p;
end; procedure swap(var a,b:point);
var c:point;
begin
c:=a;
a:=b;
b:=c;
end; function calc(x:longint):double;
var i:longint;
begin
calc:=;
if x> then
begin
for i:= to x do
calc:=calc*;
end
else if x< then
begin
for i:= to abs(x) do
calc:=calc/;
end;
end; procedure sift(i:longint);
var j,x,y:longint;
begin
j:=i shl ;
while j<=t do
begin
if (j+<=t) and (heap[j].dis>heap[j+].dis) then inc(j);
if heap[i].dis>heap[j].dis then
begin
x:=heap[i].num;
y:=heap[j].num;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=i shl ;
end
else break;
end;
end; procedure up(i:longint);
var j,x,y:longint;
begin
j:=i shr ;
while j> do
begin
if heap[i].dis<heap[j].dis then
begin
x:=heap[i].num;
y:=heap[j].num;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=j shr ;
end
else break;
end;
end; begin
readln(v,n,m);
for i:= to n do
begin
for j:= to m do
begin
read(a[i,j]);
inc(k);
num[i,j]:=k;
end;
end;
for i:= to n do
for j:= to m do
begin
vn:=v*calc(a[,]-a[i,j]);
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if num[x,y]> then add(num[i,j],num[x,y],/vn);
end;
end; n:=n*m;
t:=n;
for i:= to n do
begin
if i= then d[i]:= else d[i]:=inf;
heap[i].num:=i;
heap[i].dis:=d[i];
where[i]:=i;
end;
for i:= to n do
begin
x:=heap[].num;
mid:=heap[].dis;
if mid=inf then break;
y:=heap[t].num;
where[y]:=;
swap(heap[],heap[t]);
dec(t);
sift();
p:=w[x];
while p<>nil do
begin
y:=p^.po;
if d[y]>mid+p^.len then
begin
d[y]:=mid+p^.len;
k:=where[y];
heap[k].dis:=d[y];
up(k);
end;
p:=p^.next;
end;
end;
writeln(d[n]::);
end.
poj3037的更多相关文章
-
【POJ3037】Skiing 最短路
题意: 有个n*m的滑雪场,bessie要从(1,1)滑到(n,m),问最小时间. 起始有一个速度v,然后每从一个点A到一个点B(仅仅能上下左右走,每次一格),速度就会乘上2^(权值A-权值B). 然 ...
-
POJ3037 Skiing
Skiing 题目大意: 给定一个M*N的网格,已知在每个网格中的点可以向上下左右四个方向移动一个单位,每个点都有一个高度值. 从每个点开始移动时存在一个速度值,从A点移动到B点,则此时B点的速度为& ...
-
poj练习题的方法
poj1010--邮票问题 DFSpoj1011--Sticks dfs + 剪枝poj1020--拼蛋糕poj1054--The Troublesome Frogpoj1062--昂贵的聘礼poj1 ...
-
POJ 3037 Skiing(如何使用SPFA求解二维最短路问题)
题目链接: https://cn.vjudge.net/problem/POJ-3037 Bessie and the rest of Farmer John's cows are taking a ...
随机推荐
-
C#命名规则和编码规范
用Pascal规则来命名属性.方法.事件和类名. public class HelloWorld { public void SayHello(string name) { } } Pascal规则是 ...
-
删除win7远程桌面历史记录
开始-运行-“regedit”注册表中找到HKEY_CURRENT_USER\Software\Microsoft\Terminal Server Client\Default 删除不需要的即可
-
C#调用脚本语言(三)-- IronJS 与 IronLua 简单方法性能比较
1. 测试环境 1.1. 硬件环境 CPU:intel Core i7-740QM 内存:8GDDR3 Memory 1.2. 系统 系统:Windows 8 Enterprise 开发工具:Vs ...
-
eclipse安装lombok插件问题解决
在 java平台上,lombok 提供了简单的注解的形式来帮助我们消除一些必须有但看起来很臃肿的代码, 比如属性的get/set,及对象的toString等方法,特别是相对于 POJO.简单的说,就是 ...
-
并发编程---开启进程方式---查看进程pid
1.开启进程的两种方式 方式一: from multiprocessing import Process import time def task(name): print('%s is runnin ...
-
spring cloud 学习(一)初学SpringCloud
初学SpringCloud 前言 在SpringBoot的坑还没填完的情况下,我又迫不及待地开新坑了.主要是寒假即将结束了,到时又得忙于各种各样的事情……留个坑给自己应该就会惦记着它,再慢慢地补上…… ...
-
Z-score标准化[转载]
转自:https://blog.csdn.net/Orange_Spotty_Cat/article/details/80312154 1.意义 Z-Score通过(x-μ)/σ将两组或多组数据转化为 ...
-
Tomcat 发布项目 conf/Catalina/localhost 配置 及数据源配置
本文介绍通过在tomcat的conf/Catalina/localhost目录下添加配置文件,来发布项目.因为这样对 tomcat 的入侵性最小,只需要新增一个配置文件,不需要修改原有配置:而且支持动 ...
-
mysql 提示符显示用户,数据库等信息
命令: mysql -uroot -p --prompt="\\u@\\h:\\d \\r:\\m:\\s>" 效果: root@localhost:(mysql) 02:2 ...
-
canvas下载图片
canvas下载图片 <!DOCTYPE html> <html lang="en"> <head> <meta charset=&quo ...