http://codeforces.com/contest/677/problem/D

建颗新树,节点元素包含r、c、dis,第i层包含拥有编号为i的钥匙的所有节点。用i-1层更新i层,逐层更新到底层。

不使用就会超时的优化:用i-1层更新时不是所有节点都有必要用到,我们对i-1层排序,取前600节点更新下层。

public class Main {
private static final int c = 330,INF=Integer.MAX_VALUE/2,maxn=c*c*c+100,maxe=maxn*6;
static class Node implements Comparable<Node>{
int x,y, dis; public Node(int x, int y, int dis) {
this.x = x;
this.y = y;
this.dis = dis;
} @Override
public int compareTo(Node o) {
return dis -o.dis;
}
}
public static void main(String[] args) {
IO io=new IO();
int n=io.nextInt(),m=io.nextInt(),p=io.nextInt(); ArrayList<Node>[]al=new ArrayList[p+1];
for (int i = 0; i < al.length; i++) al[i]=new ArrayList<>(c);
int[]dis=new int[c*c];
Arrays.fill(dis,INF); for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)al[io.nextInt()].add(new Node(i,j,INF));
al[0].add(new Node(1,1,0)); int ans=INF;
for (int i=1;i<=p;i++){
Collections.sort(al[i-1]);
for (int j=0;j<Math.min(al[i-1].size(),330);j++)for (Node k:al[i]){
k.dis=Math.min(k.dis,al[i-1].get(j).dis+Math.abs(k.x-al[i-1].get(j).x)+Math.abs(k.y-al[i-1].get(j).y));
if (i==p)ans=Math.min(k.dis,ans);
}
}
io.println(ans);
}
}

最新文章

  1. 学习C的笔记
  2. Rafy 框架-发布网页版用户手册
  3. AngularJS 简介、指令、表达式
  4. winform 渐变(非API)
  5. asp.net分页控件库
  6. C# WebBrowser.DocumentCompleted 多次调用解决方法
  7. DIV+CSS 让同一行的图片和文字对齐
  8. 好的 小图标 html
  9. BZOJ:4827: [Hnoi2017]礼物
  10. 最短路径问题(dijkstra-模板)
  11. php 两个数组,若键相同,则值合并
  12. robot framework---校验新增条数功能
  13. stm8 同时使用dac和adc 采集异常,电平异常
  14. 格式化输出&amp;初始编码&amp;运算符
  15. 一个获取本机ip地址的正则
  16. corePoolSize和maxPoolSize的区别
  17. [动态库]动态库生成和使用以及Makefile编写
  18. Extjs4 页面加载先白屏后显示的bug解决
  19. java web项目配置https访问
  20. JavaScript总结(七)

热门文章

  1. 使用Linq的过程中碰到的问题
  2. CTF杂项之BubbleBabble加密算法
  3. 专注于C#.Net WPF软件开发-软件反编译-软件破解-逆向-靖芯科技-包括安卓APK反编译
  4. python学习——读取染色体长度(一、简化问题)
  5. remote: Permission to user_name/Code.git denied to other_user_name. fatal: unable to access &#39;https://github.com/user_name/Code.git/&#39;: The requested URL returned error: 403
  6. Web项目中的 /
  7. jdbc连接字符串
  8. iptables之语法
  9. 自己常用易忘的CSS样式
  10. vultr测速 看看vultr哪个地区节点速度快