2728 问题 D: 蓝桥杯2022年第十三届决赛真题-交通信号(Python组)

时间限制: 1s 内存限制: 256MB 提交: 313 解决: 19
题目描述

LQ 市的交通系统可以看成由 n 个结点和 m 条有向边组成的有向图。在每条边上有一个信号灯,会不断按绿黄红黄绿黄红黄... 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行,红灯时允许反向通行,黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立,其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时,需要观察边上的信号灯,如果允许通行则可以通过此边,在通行过程中不再受信号灯的影响;否则需要等待,直到允许通行。请问从结点 s 到结点 t 所需的最短时间是多少,如果 s 无法到达 t 则输出−1。

输入

输入的第一行包含四个整数 n, m, s, t,相邻两个整数之间用一个空格分隔。

接下来 m 行,每行包含五个整数 ui, vi, gi,ri, di ,相邻两个整数之间用一个空格分隔,分别表示一条边的起点,终点,绿灯、红灯的持续时长和距离(黄灯的持续时长)。

输出

输出一行包含一个整数表示从结点 s 到达 t 所需的最短时间。

样例输入
4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1
样例输出
11
提示

对于 40% 的评测用例,n ≤ 500 ,1 ≤ gi,ri, di ≤ 100 ;

对于 70% 的评测用例,n ≤ 5000 ;

对于所有评测用例,1 ≤ n ≤ 100000 ,1 ≤ m ≤ 200000 ,1 ≤ s, t ≤ n ,1 ≤ ui, vi ≤ n ,1 ≤ gi,ri, di ≤ 109

比赛公告

为了更好地备战即将到来的蓝桥杯国赛竞赛?,我们特别准备了蓝桥杯历年真题供大家学习和练习.