编程介的小学生 2017-09-16 11:21 采纳率: 20.5%
浏览 873
已采纳

TRAFFIC LIGHTS

Description

In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is no road connecting a junction to itself. Travel time for a road is the same for both directions. At every junction there is a single traffic light that is either blue or purple at any moment. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows

the travel times for all roads (integers),
the durations of the two colors at each junction (integers)
and the initial color of the light and the remaining time (integer) for this color to change at each junction.
Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.
Input

The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction.
The second line contains two numbers: N, M.
The following N lines contain information on N junctions. The (i+2)’th line of the input file holds information about the junction i : Ci, ric, tiB, tiP where Ci is either ‘B’ or ‘P’, indicating the initial color of the light at the junction i.
Finally, the next M lines contain information on M roads. Each line is of the form: i, j, lij where i and j are the id-numbers of the junctions which are connected by this road .

2 <= N <=300 where N is the number of junctions. The junctions are identified by integers 1 through N. These numbers are called id-numbers.
1 <=M <=14,000 where M is the number of roads.
1 <= lij <= 100 where lij is the time required to move from junction i to j using the road that connects i and j.
1 <= tic <= 100 where tic is the duration of the color c for the light at the junction i. The index c is either B for blue or P for purple.
1 <= ric <= tic where ric is the remaining time for the initial color c at junction i.
The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction.
The second line contains two numbers: N, M.
The following N lines contain information on N junctions. The (i+2)’th line of the input file holds information about the junction i : Ci, ric, tiB, tiP where Ci is either ‘B’ or ‘P’, indicating the initial color of the light at the junction i.
Finally, the next M lines contain information on M roads. Each line is of the form: i, j, lij where i and j are the id-numbers of the junctions which are connected by this road .
Output

If a path exists:

The first line will contain the time taken by a minimum-time path from the source junction to the destination junction.

If a path does not exist:

A single line containing only the integer 0.
Sample Input

1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
Sample Output

127

  • 写回答

1条回答 默认 最新

  • devmiao 2017-09-16 16:27
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题