题目背景
在某教练的强迫之下,我一个蒟蒻居然又出题了!!!出题了!!!(数据太水别找我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;}