热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【题解】LuoGu3393:逃离僵尸岛

原题传送门题目描述小a住的国家被僵尸侵略了!小a打算逃离到该国唯一的国际空港逃出这个国家。该国有N个城市,城市之间有道路相连。一共有M条双向道路。保

原题传送门
题目描述

小a住的国家被僵尸侵略了!小a打算逃离到该国唯一的国际空港逃出这个国家。

该国有N个城市,城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。

K个城市已经被僵尸控制了,如果贸然闯入就会被感染TAT…所以不能进入。由其中任意城市经过不超过S条道路就可以到达的别的城市,就是危险城市。换句话说只要某个没有被占城市到某个被占城市不超过s距离,就是危险。

小a住在1号城市,国际空港在N号城市,这两座城市没有被侵略。小a走每一段道路(从一个城市直接到达另外一个城市)得花一整个白天,所以晚上要住旅店。安全的的城市旅馆比较便宜要P元,而被危险的城市,旅馆要进行安保措施,所以会变贵,为Q元。所有危险的城市的住宿价格一样,安全的城市也是。在1号城市和N城市,不需要住店。

小a比较抠门,所以他希望知道从1号城市到N号城市所需要的最小花费。

输入数据保证存在路径,可以成功逃离。输入数据保证他可以逃离成功。

输入输出格式

输入格式:
第一行4个整数(N,M,K,S)

第二行2个整数(P,Q)

接下来K行,ci,表示僵尸侵占的城市

接下来M行,ai,bi,表示一条无向边

输出格式:
一个整数表示最低花费
输入样例
13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13
输出样例
11000
对于100%数据,2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000

【题解】
读完题目我发现这是一道裸的最短路~~~
只是多了一个判断是否为危险城市的步骤
本题分为以下几个步骤


  • 把感染的城市标记,这些城市是不通的,并放进一个bfs队列
  • 从感染的城市出发进行bfs&#xff0c;把遍历到的距离<&#61;s的标记为危险城市&#xff08;危险城市与感染城市是不同的&#xff09;
  • 以1为起点&#xff0c;做最短路&#xff0c;我刚学了dijkstra堆优化&#xff0c;所以用了这个方法&#xff0c;本题也可以用SPFA

嗯没错&#xff0c;这就是一道模板题&#xff0c;解释一下我的代码的各个变量的用途


  • heap 堆&#xff08;由于我用的是pascal&#xff0c;所以是手打堆&#xff09;
  • q,d 用于bfs&#xff0c;q记录点的序号&#xff0c;d记录该点离最近的感染城市的距离
  • edge,head 数组模拟链表存图
  • flag 标记感染城市 danger 标记危险城市 vis 用于dijkstra
  • dis 表示距离&#xff0c;用于dijkstra

注意&#xff1a;开int64(long long)&#xff0c;并且初始化dis也要弄得很大很大&#xff0c;比2147483647还要大

Code&#xff1a;

varheap:array[0..1000000] of recordnum,dis:int64;end;edge:array[0..1000000] of recordt,next:int64;end;head,q,d,dis:array[0..1000000] of int64;vis,danger,flag:array[0..1000000] of boolean;n,m,k,s,p,qq,x,y,z,h,t,num,len,e,w:int64;i:longint;procedure add(x,y:int64);begininc(num);edge[num].t :&#61; y;edge[num].next :&#61; head[x];head[x] :&#61; num;
end;procedure swap(var x,y:int64);
vartmp:int64;begintmp :&#61; x; x :&#61; y; y :&#61; tmp;
end;procedure push(x,y:int64);
vari:longint;begininc(len);heap[len].num :&#61; x; heap[len].dis :&#61; y;i :&#61; len;while i > 1 dobeginif heap[i].dis > 1].dis thenbeginswap(heap[i].num,heap[i >> 1].num);swap(heap[i].dis,heap[i >> 1].dis);i :&#61; i >> 1;end else break;end;
end;procedure pop;
vari,x:longint;beginheap[1].num :&#61; heap[len].num; heap[1].dis :&#61; heap[len].dis;dec(len); i :&#61; 1;while (i <<1) <&#61; len dobeginif ((i <<1 or 1) > len) or (heap[i <<1].dis 1 or 1].dis) thenx :&#61; i <<1 else x :&#61; i <<1 or 1;if heap[i].dis > heap[x].dis thenbeginswap(heap[i].num,heap[x].num);swap(heap[i].dis,heap[x].dis);i :&#61; x;end else break;end;
end;beginreadln(n,m,k,s);readln(p,qq);for i :&#61; 1 to k dobeginreadln(q[i]);flag[q[i]] :&#61; true;end;for i :&#61; 1 to m dobeginreadln(x,y);add(x,y); add(y,x);end;t :&#61; k;while h dobegininc(h);if d[h] &#61; s then break;i :&#61; head[q[h]];while i <> 0 dobegine :&#61; edge[i].t;if not danger[e] thenbegindanger[e] :&#61; true;inc(t);q[t] :&#61; e; d[t] :&#61; d[h] &#43; 1;end;i :&#61; edge[i].next;end;end;for i :&#61; 2 to n do dis[i] :&#61; maxlongint * maxlongint;heap[1].num :&#61; 1; heap[1].dis :&#61; 0; len :&#61; 1;while len > 0 dobeginx :&#61; heap[1].num; y :&#61; heap[1].dis;pop;if vis[x] then continue;vis[x] :&#61; true;i :&#61; head[x];while i <> 0 dobegine :&#61; edge[i].t;if flag[e] thenbegini :&#61; edge[i].next;continue;end;if danger[e] then w :&#61; qq else w :&#61; p;if e &#61; n then w :&#61; 0;if dis[e] > y &#43; w thenbegindis[e] :&#61; y &#43; w;push(e,dis[e]);end;i :&#61; edge[i].next;end;end;writeln(dis[n]);
end.

推荐阅读
  • 深入解析Java虚拟机(JVM)架构与原理
    本文旨在为读者提供对Java虚拟机(JVM)的全面理解,涵盖其主要组成部分、工作原理及其在不同平台上的实现。通过详细探讨JVM的结构和内部机制,帮助开发者更好地掌握Java编程的核心技术。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本题要求在一组数中反复取出两个数相加,并将结果放回数组中,最终求出最小的总加法代价。这是一个经典的哈夫曼编码问题,利用贪心算法可以有效地解决。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置,以及包转发率性能测试小慢哥的原创文章,欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • 作者:守望者1028链接:https:www.nowcoder.comdiscuss55353来源:牛客网面试高频题:校招过程中参考过牛客诸位大佬的面经,但是具体哪一块是参考谁的我 ... [详细]
  • FinOps 与 Serverless 的结合:破解云成本难题
    本文探讨了如何通过 FinOps 实践优化 Serverless 应用的成本管理,提出了首个 Serverless 函数总成本估计模型,并分享了多种有效的成本优化策略。 ... [详细]
  • 开发笔记:9.八大排序
    开发笔记:9.八大排序 ... [详细]
  • 本文详细探讨了HTML表单中GET和POST请求的区别,包括它们的工作原理、数据传输方式、安全性及适用场景。同时,通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]
  • 深入解析Redis内存对象模型
    本文详细介绍了Redis内存对象模型的关键知识点,包括内存统计、内存分配、数据存储细节及优化策略。通过实际案例和专业分析,帮助读者全面理解Redis内存管理机制。 ... [详细]
  • LeetCode: 实现队列与栈的高级应用
    本文介绍如何使用队列和栈实现特定功能,包括动态维护队列元素并计算其平均值,以及栈操作中的优化技巧。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 深入解析TCP/IP五层协议
    本文详细介绍了TCP/IP五层协议模型,包括物理层、数据链路层、网络层、传输层和应用层。每层的功能及其相互关系将被逐一解释,帮助读者理解互联网通信的原理。此外,还特别讨论了UDP和TCP协议的特点以及三次握手、四次挥手的过程。 ... [详细]
  • 本文详细介绍了优化DB2数据库性能的多种方法,涵盖统计信息更新、缓冲池调整、日志缓冲区配置、应用程序堆大小设置、排序堆参数调整、代理程序管理、锁机制优化、活动应用程序限制、页清除程序配置、I/O服务器数量设定以及编入组提交数调整等方面。通过这些技术手段,可以显著提升数据库的运行效率和响应速度。 ... [详细]
author-avatar
dajiang
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有