Dotcpp  /  编程题库  /  蓝桥杯2022年第十三届决赛真题-交通信号（C/C++/Java组）
题目 2715:

蓝桥杯2022年第十三届决赛真题-交通信号（C/C++/Java组）

 时间限制: 1s 内存限制: 256MB

题目描述

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 。 

标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
蓝桥杯2025年第十六届省赛真题-画展布置
蓝桥杯2025年第十六届省赛真题-生产车间
蓝桥杯2025年第十六届省赛真题-装修报价
蓝桥杯2025年第十六届省赛真题-水质检测
蓝桥杯2025年第十六届省赛真题-电池分组