n<=100 * m<=100的地图,每个数绝对值不超过25,从1,1到n,m,一开始速度v,从数字A走到数字B速度会变成v*2^(A-B),求到终点最短时间。

可以发现,相同的数字出发的速度是一样的,和(1,1)位置的数的差做2的指数再乘v,而一个点只有四条边,跑个最短路即可。

然后n,m打反调了1.5h。。

 #include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
//#include<iostream>
using namespace std; int n,R,C,v;
#define maxn 10011
#define maxm 80011
int a[][];double pw[];
struct Graph
{
struct Edge{int to,next;double v;}edge[maxm];int first[maxn],le;
Graph() {memset(first,,sizeof(first));le=;}
void in(int x,int y,double v) {Edge &e=edge[le];e.to=y;e.v=v;e.next=first[x];first[x]=le++;}
double dis[maxn];bool vis[maxn];
struct qnode
{
int id;double v;
bool operator > (const qnode &b) const {return v>b.v;}
};
priority_queue<qnode,vector<qnode>,greater<qnode> > q;
double dijkstra(int s,int t)
{
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) dis[i]=1e15;dis[s]=;
q.push((qnode){s,});
while (!q.empty())
{
const int now=q.top().id;const double d=q.top().v;q.pop();
if (vis[now]) continue;
vis[now]=;
for (int i=first[now];i;i=edge[i].next)
{
const Edge &e=edge[i];
if (dis[e.to]>d+e.v)
{
dis[e.to]=d+e.v;
q.push((qnode){e.to,dis[e.to]});
}
}
}
return dis[t];
}
}g;
int main()
{
pw[]=1.0;
for (int i=;i<=;i++) pw[i]=pw[i-]*;
for (int i=-;i>=-;i--) pw[i]=pw[i+]/;
scanf("%d%d%d",&v,&R,&C);
for (int i=;i<=R;i++)
for (int j=;j<=C;j++)
scanf("%d",&a[i][j]);
n=R*C;
for (int i=;i<=R;i++)
for (int j=;j<=C;j++)
{
double now=1.0/(pw[a[][]-a[i][j]]*v);
int id=(i-)*C+j;
if (j>) g.in(id,id-,now);
if (j<C) g.in(id,id+,now);
if (i>) g.in(id,id-C,now);
if (i<R) g.in(id,id+C,now);
}
printf("%.2f\n",g.dijkstra(,n));
return ;
}

最新文章

  1. geotrellis使用(二十三)动态加载时间序列数据
  2. 多台服务器最好加上相同的machineKey
  3. chorme模拟微信浏览器
  4. HeaderTemplate
  5. CANoe 入门 Step by step系列(二)CAPL编程【转】
  6. 用jquery修改默认的单选框radio或者复选框checkbox选择框样式
  7. HTML5拖放
  8. C# 解析嵌套的json文件.
  9. svg动画学习
  10. do from a specific ip
  11. 为什么Java大数据是最火爆的编程语言?
  12. java截取一个字符串正数或倒数某个特定字符前后的内容
  13. 实战深度学习(上)OpenCV库
  14. [Codeforces741D]Arpa&#39;s letter-marked tree and Mehrdad&#39;s Dokhtar-kosh paths——dsu on tree
  15. 什么是ip代理
  16. Linux服务器超简单安装Python3环境、Ipython、Jupyter、virtualenv、virtualenvwrapper教程全在这了
  17. 在SpringBoot中使用热部署(DevTools)
  18. Atitit 遍历文件夹算法 autoit attilax总结
  19. iOS &amp;Android 项目 Jenkins持续集成
  20. Tomcat启动慢原因之二 he APR based Apache Tomcat Native library which allows optimal performance in production environments was not found on the java.library.path

热门文章

  1. 转 Java 208道面试题及部分答案 补充部分答案
  2. logging日志过滤和日志文件自动截取
  3. random模块详解
  4. windows session logoff时进行处理动作
  5. 升级或者重装Discuz! 版本后 QQ互联英文乱码显示的正确解决方法
  6. 数组排序 sort
  7. iview table 勾选当前行代码 data key _checked: true
  8. 搜索 || DFS || UOJ 146 信息传递
  9. SQL Server查看表的约束
  10. java中HashMap,LinkedHashMap,TreeMap,HashTable的区别