Skip to content

14335: 【原4335】城市道路

题目

题目描述

author: smallling 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4335

Description

有$n$个城市,标号$1\sim n$,这些城市有$m$组双向道路。

每一组双向道路由两个区间$[a_i,b_i],[c_i,d_i]$表示,对于城市$u\in[a_i,b_i]$都有一条双向道路连接城市$v\in[c_i,d_i]$。

对于首都$p$,求从$p$到所有城市所需经过的最少道路数量。

Input Format

第一行,三个正整数$n,m,p$。

接下来$m$行,每行四个正整数$a_i, b_i, c_i, d_i$。

$n\leq 5*10^5,m\leq 10^5, 1\leq a_i \leq b_i \leq n, 1\leq c_i \leq d_i \leq n,[a_i, b_i]\cap[c_i,d_i]=\emptyset$

Output Format

输出$n$行,每行一个整数,第$i$行表示从$p$到$i$所需经过的最少道路数量(保证可达)。

Sample Input

5 3 4
1 2 4 5
5 5 4 4
1 1 3 3

Sample Output

1
1
2
0
1

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!