神奇的道路
发布日期:2022-03-15 04:11:15 浏览次数:36 分类:技术文章

本文共 2165 字,大约阅读时间需要 7 分钟。

题目背景

在某教练的强迫之下,我一个蒟蒻居然又出题了!!!出题了!!!(数据太水别找我qwq)

好的,JL说好的一题100快拿来

题目描述

我们有一个有向图,每条边权值为1,我们要在上面找一条神奇的道路满足:

1.神奇的道路上的所有点的出边所指向的点都直接或间接与终点连通。

2.在满足条件1的情况下使路径最短。

3.该路径是从起点到终点的路径

垃圾出题人表示找不到这条路径,所以希望你帮忙qwq

输入格式

第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n个点和 m 条边。

接下来的 m 行每行 2 个整数 x,y,之间用一个空格隔开,表示有一条边从点 x 指向点y。

最后一行有两个用一个空格隔开的整数 s, t,表示起点为 s,终点为 t。

输出格式

输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路径不存在,输出“orz”(不含双引号)

输入输出样例

输入#1

3 2  1 2  2 1  1 3

输出#1

orz

输入#2

7 85 23 15 31 63 66 72 72 45 7

输出#2

3

说明/提示

对于样例一: 起点1与终点3不连通,所以满足题目描述的路径不存在,故输出orz。

数据范围

30%保证是连通图

100% 0<n≤10000,0<m≤200000,0<x,y,s,t≤n,x,s≠t。

 

 

早上毒瘤出题人告诉我跑最长路有60分。。。。。。

 

#include 
#include
#include
using namespace std;int tot,total,n,m,ss,tt,l[500050],r[500050],pre[500050],last[10050],other[500050];int que[10050],d[10050];bool judge[10050],vis[10050],point[10050];inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-'){ w=-1; } ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*w;}void add(int u,int v) { pre[++tot]=last[u]; last[u]=tot; other[tot]=v;}void bfs(int x) { int h=0,t=1; que[1]=x; vis[x]=1; point[x]=1; total++; while (h
d[cur]+1) { d[q]=d[cur]+1; if (!vis[q]) { vis[q]=1; que[++t]=q; } } } }}int main() { n=read(); m=read(); for (int i=1; i<=m; i++){ l[i]=read(); r[i]=read(); } ss=read(); tt=read(); for (int i=1; i<=m; i++) add(r[i],l[i]); bfs(tt); if (!point[ss]) { printf("orz\n"); return 0; } for (int i=1; i<=n; i++) { if (point[i]) continue; for (int p=last[i]; p; p=pre[p]) { int q=other[p]; judge[q]=1; } } memset(que,0,sizeof que); memset(vis,0,sizeof vis); memset(last,0,sizeof last); tot=0; for (int i=1; i<=m; i++) add(l[i],r[i]); spfa(ss); printf("%d",d[tt]); return 0;}

 

转载于:https://www.cnblogs.com/hrj1/p/11357179.html

转载地址:https://blog.csdn.net/weixin_30536513/article/details/99776878 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hapRroxy 安装配置详解
下一篇:模块与包

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月26日 04时55分43秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章