4260. 原神nb

【题目背景】

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

【题目描述】

原神的须弥城有n个建筑组成，由于须弥城太大了，于是创造了一个机器用于连接两个建筑群，即从[l1,r1]到[l2,r2]是一条长度为v的路径，共有m条路径，你需要计算从智慧宫（起点s）到每个节点的最短通行时间（若无法到达则输出-1）。

【输入格式】

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

接下来 m 行，每行五个正整数为，l1,r1,l2,r2,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≤n≤10^3,1≤m≤10^3 ,对于所有的区间均满足l=r

对于 50% 的数据，  1≤n≤10^4,1≤m≤10^4

对于 100% 的数据，  1≤n≤10^5,1≤m≤2×10^5,1≤v≤10^9,1≤s≤n,1≤l,r≤n,l≤r。

【来源】

wxs的题目