1807. [NOIP2014]寻找道路P2296 寻找道路
2024-09-08 02:24:44
题目描述
在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
1 .路径上的所有点的出边所指向的点都直接或间接与终点连通。
2 .在满足条件1 的情况下使路径最短。
注意:图G 中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入输出格式
输入格式:
输入文件名为road .in。
第一行有两个用一个空格隔开的整数n 和m ,表示图有n 个点和m 条边。
接下来的m 行每行2 个整数x 、y ,之间用一个空格隔开,表示有一条边从点x 指向点y 。
最后一行有两个用一个空格隔开的整数s 、t ,表示起点为s ,终点为t 。
输出格式:
输出文件名为road .out 。
输出只有一行,包含一个整数,表示满足题目᧿述的最短路径的长度。如果这样的路径不存在,输出- 1 。
输入输出样例
输入样例#1:
3 2
1 2
2 1
1 3
输出样例#1:
-1
输入样例#2:
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
输出样例#2:
3
说明
解释1:
如上图所示,箭头表示有向道路,圆点表示城市。起点1 与终点3 不连通,所以满足题
目᧿述的路径不存在,故输出- 1 。
解释2:
如上图所示,满足条件的路径为1 - >3- >4- >5。注意点2 不能在答案路径中,因为点2连了一条边到点6 ,而点6 不与终点5 连通。
对于30%的数据,0<n≤10,0<m≤20;
对于60%的数据,0<n≤100,0<m≤2000;
对于100%的数据,0<n≤10,000,0<m≤200,000,0<x,y,s,t≤n,x≠t。
这道题我们可以用逆向思维来想
如果一个点能到达终点,那么终点也一定能到达这个点
这样就简单了
从终点跑一遍BFS,算出每一个点的访问次数
然后把不能走的点删去
最后spfa带走
一个很有意思的能够找出访问次数而且不会死循环的方法
int to=edge[i].v;
if(cs[to]++)continue;
q.push(to);
完整代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define INF 0x7ffffff
using namespace std;
int read(int & n)
{
int flag=,x=;char c='/';
while(c<''||c>''){c=getchar();if(c=='-')flag=;}
while(c>=''&&c<='')x=x*+(c-),c=getchar();
if(flag)n=-x;else n=x;
}
const int MAXN=;
int n,m,bgx,bgy;
int rudu[MAXN];
struct node
{
int u,v,w,nxt;
}edge[MAXN];
int num=;
int head[MAXN];
int flag[MAXN];// 记录每个值是否能够到达终点
int cs[MAXN];
int dis[MAXN];
int vis[MAXN];
void add_edge(int ll,int rr,int ww)
{
edge[num].u=ll;
edge[num].v=rr;
edge[num].w=ww;
edge[num].nxt=head[ll];
head[ll]=num++;
}
void bfs()
{
queue<int>q;
int tot=;
q.push(bgx),tot++;
while(q.size()!=)
{
int p=q.front();
q.pop();
for(int i=head[p];i!=-;i=edge[i].nxt)
{
int to=edge[i].v;
if(cs[to]++)continue;
q.push(to);
}
}
//rudu[bgy]=0;
for(int i=;i<=n;i++)
if(rudu[i]!=cs[i]&&i!=bgy)
flag[i]=;
}
void dele()
{
for(int i=;i<=num;i++)
{
if(flag[edge[i].u]!=)
{
edge[i].u=-;
edge[i].v=-;
edge[i].w=-;
edge[i].nxt=-;
}
}
}
void spfa()
{
queue<int>q;
q.push(bgx);
dis[bgx]=;
while(q.size()!=)
{
int p=q.front();
q.pop();
vis[p]=;
for(int i=head[p];i!=-;i=edge[i].nxt)
{
if(edge[i].u==-)continue;
int to=edge[i].v;
if(dis[to]>dis[p]+edge[i].w)
{
dis[to]=dis[p]+edge[i].w;
if(vis[to]==)
{
vis[to]=;
q.push(to);
}
}
}
}
if(dis[bgy]==INF)
printf("-1");
else
printf("%d",dis[bgy]);
}
int main()
{
freopen("roadb.in","r",stdin);
freopen("roadb.out","w",stdout);
read(n);read(m);
for(int i=;i<=n;i++)head[i]=-,dis[i]=INF;
for(int i=;i<=m;i++)
{
int x,y;
read(x);read(y);
add_edge(y,x,);
rudu[x]++;
}
read(bgy);read(bgx);
bfs();
dele();
spfa();
return ;
}
最新文章
- Android进阶系列之源码分析Activity的启动流程
- 安装使用Oracle OSWbb/OSWbba工具
- ORACLE触发器判断是否更新了某个字段
- Squid代理服务器的安装与配置
- Android Activity切换动画overridePendingTransition
- WCF X.b 操作引用了已经从 Y.b 操作导出的消息元素 [http://tempuri.org/:b]。可以通过更改方法名称或使用 OperationContractAttribute 的 Name 属性更改其中一个操作的名称...
- leetcodequestion_56 Merge Intervals
- linux_删除空文件(大小等于0的文件)的方法
- 转: 两个 Shell 网站: explainshell 和 shellcheck
- 封装一个button上带图片的,图片在上,文字在下的按钮
- AndroidStudio加快Gradle速度的方法-android study之旅(103)
- HDU2035
- Mysql 日期加减
- sql server 小技巧(2) 删除sql server中重复的数据
- js 创建Date对象5种方式
- Sqoop导入HBase,并借助Coprocessor协处理器同步索引到ES
- iOS 新浪微博-1.0框架搭建
- POC索引
- (转)Python random模块
- bzoj [POI2005]Kos-Dicing 二分+网络流
热门文章
- pymongo collection.save 问题
- form 表单序列化 serialize
- 设计并实现一个LRU Cache
- java.lang.IllegalArgumentException: sheetName &;#39;&;#39; is invalid
- 使用bbed改动数据
- centos内核编译配置
- 关于jiffies回绕以及time_after,time_before
- Python常用数据处理函数
- 图像处理之基础---滤波器之高斯低通滤波器3c代码实现yuv,rgb
- QQ空间说说 视频播放