【luogu P3393 逃离僵尸岛】 题解
2024-10-07 14:21:29
题目链接:https://www.luogu.org/problemnew/show/P3393
被占领的点可以先连在一个点上然后只需要对这一个点bfs一遍就可以求所有的危险点
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2 * 1e5 + 10;
ll n, m, k, s, val[2], danger[maxn], ddis[maxn], dis[maxn], charge[maxn], v[maxn], u[maxn];
bool vis[maxn], vvis[maxn];
struct edge{
ll from, to, next, len;
}e[maxn<<2], ee[maxn<<2];
ll cnt, head[maxn], cntt, headd[maxn];
queue<ll> dq, q;
void add(ll u, ll v, ll w)
{
e[++cnt].from = u;
e[cnt].len = w;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
void ad(ll u, ll v, ll w)
{
ee[++cntt].from = u;
ee[cntt].len = w;
ee[cntt].next = headd[u];
ee[cntt].to = v;
headd[u] = cntt;
}
void SPFA()
{
while(!q.empty())
{
ll now = q.front(); q.pop();
vis[now] = 0;
for(ll i = head[now]; i != -1; i = e[i].next)
{
if(dis[e[i].to] > dis[now] + e[i].len && danger[e[i].to] == 0)
{
dis[e[i].to] = dis[now] + e[i].len;
if(!vis[e[i].to])
{
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
}
}
void BFS()
{
while(!dq.empty())
{
ll now = dq.front(); dq.pop();
vis[now] = 0;
for(ll i = headd[now]; i != -1; i = ee[i].next)
{
if(ddis[ee[i].to] > ddis[now] + ee[i].len)
{
ddis[ee[i].to] = ddis[now] + ee[i].len;
if(!vvis[ee[i].to])
{
dq.push(ee[i].to);
vvis[ee[i].to] = 1;
}
}
}
}
}
int main()
{
memset(head, -1, sizeof(head));
memset(headd, -1, sizeof(headd));
memset(dis, 127, sizeof(dis));
memset(ddis, 127, sizeof(ddis));
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&s,&val[0],&val[1]);
for(ll i = 1; i <= k; i++)
{
ll u;
scanf("%lld",&u);
danger[u] = 1;
ad(u, 0, 1);
ad(0, u, 1);
}
for(ll i = 1; i <= m; i++)
{
scanf("%lld%lld",&u[i],&v[i]);
ad(u[i], v[i], 1);
ad(v[i], u[i], 1);
}
dq.push(0), ddis[0] = 0, vvis[0] = 1;
BFS();
for(ll i = 1; i <= n; i++)
if(ddis[i] <= s+1)
charge[i] = 1;
for(ll i = 1; i <= m; i++)
{
if(danger[u[i]] != 1 && danger[v[i]] != 1)
{
add(u[i], v[i], val[charge[v[i]]]);
add(v[i], u[i], val[charge[u[i]]]);
}
}
q.push(1), dis[1] = 0, vis[1] = 1;
SPFA();
/*for(ll i = 0; i <= n; i++)
cout<<charge[i]<<" ";*/
printf("%lld",dis[n]-val[charge[n]]);
return 0;
}
最新文章
- Linux内核的文件预读readahead
- JavaScript——Prototype详探
- CentOS6.5上编译OpenJDK7源码
- c# 改变图片的大小(w,h)
- C++内嵌汇编代码,简单文件加密
- ClassLoader,Thread.currentThread().setContextClassLoader,tomcat的ClassLoader
- Moses创建一个翻译系统的基本过程记录,以后会按照每个过程详细说明,并给出每个步骤的参数说明
- struts2面试题
- HDU1584:蜘蛛牌(DFS)
- How to make workflow chart using several tools in Linux?
- 201521123016 《Java程序设计》第7周学习总结
- C# 中函数内定义函数的委托方法
- 列出JDK中常用的Java包
- 基于Spring和Mybatis拦截器实现数据库操作读写分离
- tensorflow 学习纪录(持续更新)
- 没有-jackson相关依赖会抛出如下异常--------在spring官方文档有解释
- oracle单行函数 之 时间函数
- Application_Start 多次启动问题
- C++空类产生哪些成员函数 || C++类可以自动生成的6个成员函数
- session.upload_progress.enabled开启的问题
热门文章
- Oracle Spatial GIS相关研究
- csharp:using Newtonsoft.Json.Net2.0 in .net 2.0 webform
- [ERROR] Failed to execute goal org.apache.maven.plugins:maven-dependency-plugin:2.8:unpack (unpack) on project sq-integral-web: Unable to find artifact.
- <;Android 应用 之路>; MPAndroidChart~LineChart
- hdu 3367 Pseudoforest (最大生成树 最多存在一个环)
- geoserver 知识小计
- SQLite入门(二)读写二进制数据
- Python unittest模块心得(一)
- 使用 Azure CLI 将 IaaS 资源从经典部署模型迁移到 Azure Resource Manager 部署模型
- SQL Server ->;>; Sparse File(稀疏文件)