4260. 原神nb

【题目背景】

你知道吗，原神真的很牛逼

【题目描述】

原神的须弥城有 $n$ 个建筑组成，由于须弥城太大了，于是创造了一个机器用于连接两个建筑群，任意序号在 $[l_1,r_1]$ 中的点到序号在 $[l_2,r_2]$ 的点有一条长度为 $v$ 的路径，共有 $m$ 种这样的路径，你需要计算从智慧宫（起点 $s$）到每个节点的最短通行时间（若无法到达则输出 $-1$）。

【输入格式】

第一行包含三个整数 $n,m,s$，分别表示节点数量、路径数量、起点编号。

接下来 $m$ 行，每行五个正整数为，$l_1,r_1,l_2,r_2,v$，意义见题面。输出格式

【输出格式】

输出 $n$ 行，第 $i$ 行表示从 $S$ 到节点 $i$ 的最短通行时间；若无法到达，输出 $−1$。

【样例输入】

8 7 1
1 1 2 3 2
2 4 5 5 1
1 1 4 6 3
3 5 6 7 2
4 4 6 8 2
1 7 8 8 1
2 3 7 8 4

【样例输出】

0
2
2
3
3
3
4
1

【样例说明】

原神nb，所以你要自己试

【数据规模与约定】

对于 $20\%$ 的数据，$1 \le n \le 10^3$，$1 \le m \le 10^3$，对于所有的区间均满足 $l=r$。

对于 $50\%$ 的数据，$1 \le n \le 10^4$，$1 \le m \le10^4$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le v \le 10^9$，$1 \le s \le n$，$1 \le l,r\le n$，$l \le r$。

【来源】

wxs的题目