文档章节

11.15 寻找道路

Loi_DL
 Loi_DL
发布于 2016/11/15 15:44
字数 482
阅读 6
收藏 0

https://www.luogu.org/problem/show?pid=2296#sub

题面丢在这  ↑  (*^__^*) 嘻嘻……

题解 : 刚开始看了一会没看明白怎么弄,看明白题意了,然后不会判断一个点的出边所指向的点是否与终点连通,貌似可以反向建边,dfs一边如果能跑到就标记一下,没标记的都是不能跑到的,然后正向建边,判断每个点是否与终点连通如果连通,可以遍历这个点能到的所有点是否与终点连通,连通就标记一下,在spfa的过程中判断如果这个点可以用并且符合最短路更新条件就可以更新否则不更新。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n,m,s,e;
int x[500000],y[500000];
struct edge
{
	int f,t,d;
}es[500000];
int tot=0,first[500000],next[500000],dis[500000];
void jt(int f,int t,int d)
{
	es[++tot]=(edge){f,t,d};
	next[tot]=first[f];
	first[f]=tot;
}
int ky[500000];
void dfs(int x)
{
	ky[x]=1;
	for(int i=first[x];i!=0;i=next[i])
	{
		int v=es[i].t;
		if(ky[v]==0)
		dfs(v);
	}
	return ;
}
void init()
{
	tot=0;
	memset(first,0,sizeof(first));
	memset(next,0,sizeof(next));
	memset(dis,0,sizeof(dis));
	memset(es,0,sizeof(es));
}
queue <int> q;
bool vis[500000],used[500000];
void spfa(int s)
{
	for(int i=1;i<=n;i++)
		dis[i]=1e9+7;
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while (!q.empty())
	{
		int f=q.front();
		q.pop();
		vis[f]=0;
		for(int i=first[f];i!=0;i=next[i])
		{
			int v=es[i].t;
			if(used[v]==1&&dis[v]>dis[f]+es[i].d)
			{
				dis[v]=dis[f]+es[i].d;
				if(vis[v]==0)
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		jt(y[i],x[i],1);
	}
	scanf("%d%d",&s,&e);
	dfs(e);
	init();
	for(int i=1;i<=m;i++)
		jt(x[i],y[i],1);
	for(int i=1;i<=n;i++)
	{
		int h=0;
		for(int j=first[i];j!=0;j=next[j])
		{
			int v=es[j].t;
			if(ky[v]==0)
			{
				h=1;
				break;
			}
		}
		if(h==0)
		used[i]=1;
	}
	spfa(s);
	if(dis[e]==1e9+7)
	printf("-1");
	else 
	printf("%d",dis[e]);
	return 0;
}

 

© 著作权归作者所有

上一篇: 记忆化搜索
下一篇: 11.12 T3
Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
Calculate Linux 11.15 发布

Calculate Linux是基于Gentoo的三份卓越发行之集合。Calculate Directory Server(CDS)是通过LDAP加SAMBA来支持Windows和Linux客户端的解决方案,它提供代理、邮件、Jabbers服务器,并带有 ...

红薯
2012/03/14
616
0
李雯 2016-11-28 工作日报

8:00~10:30 業務内容: 1>处理 Amazon 网络订单15张 成果: 1.友盛売上伝票15张 3.友利仕入伝票15张 4.送り状42张 10:30~12:00 業務内容: 1>到yamato网站下载精算书,制作11.30yamato2016.11....

ribunn
2016/11/28
2
0
李雯 2016-11-29 工作日报

8:00~9:30 業務内容: 1>处理 Amazon 网络订单8张 成果: 1.友盛売上伝票8张 2.友利売上伝票8张 3.友利仕入伝票8张 4.送り状8张 9:30~12:00 業務内容: 根据11.17amazon2016.11.1-11.15入金明细...

ribunn
2016/11/30
1
0
李雯 2016-12-1 工作日报

8:00~9:00 業務内容: 1>处理 Amazon 网络订单5张 成果: 1.友盛売上伝票5张 2.友利売上伝票5张 3.友利仕入伝票5张 4.送り状5张 9:00~12:00 業務内容: 根据11.18Amazon2016.11.1-11.15入金明细...

ribunn
2016/12/01
1
0
电视节目《战胜贫穷》(大型纪实真人秀)

战胜贫穷(大型纪实真人秀) 1.通过全国选拔不同行业的工程师、志愿者,起草方案、组织人员、工具,寻找赞助商, 为贫困地区改善生存环境,创造自给自足的条件,帮助他们解决生存问题。 2.供...

Mooke
2015/08/10
26
0

没有更多内容

加载失败,请刷新页面

加载更多

Rabbit MQ 延迟消息发送

为什么使用延迟消息? 不同于同步消息,有些业务场景下希望可以实现延迟一定时间再消费消息。 典型的场景有微信、支付宝等第三方支付回调接口,会在用户支付后3秒、5秒、30秒等等时间后向应用...

兜兜毛毛
5分钟前
0
0
【0918】正则介绍_grep

【0918】正则介绍_grep 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 一、正则介绍 正则是一串有规律的字符串,它使用单个字符串来描述或匹配一系列符合某个语法规则的字符串。 二、grep工具 ...

飞翔的竹蜻蜓
35分钟前
4
0
为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
今天
8
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
今天
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部