### fimaji1688's blog

By fimaji1688, history, 6 weeks ago,

There is a network of interconnected water pipes such that:

-There is no more than one pipe connecting two intersections1. -There is no pipe that loops around to the same intersection -The time taken by water to flow through a pipe is equal to the length of the pipe and is the same in both directions At every intersection there is a valve such that:

The valve opens at specific intervals, say after every T seconds The time interval T is different for each intersection Water can only flow through an intersection when the valve is open If water arrives when the valve is closed, then it stops till the valve opens again If water arrives at the intersection at the exact time the valve is open then it flows without delay Input Format

First line contains two integers: source and destination intersections Second line contains two integers: X (total number of intersections) & Y (total number of pipes) Third line contains X integers, specifying the time interval T for each intersection Next Y lines contain 3 integers each, specifying details of each pipe — the two intersections that the pipe connects, as well as the length L of the pipe Output Format A single integer which is the time taken by water to flow between the source and destination intersections

Example Input 1:
1 6
6 8
6 4 2 5 4 8
1 2 3
1 3 7
2 3 4
2 4 10
3 5 8
4 5 3
4 6 10
5 6 6
Example Output 1: 22

Example Input 2:
1 5
5 6
5 3 7 2 10
1 2 10
1 3 2
2 5 10
2 4 2
3 5 18
4 5 3

Example Output 2: 17


• -17

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by fimaji1688 (previous revision, new revision, compare).
 » 6 weeks ago, # |   +18 how can we know that this is not from a running competition?
•  » » 6 weeks ago, # ^ |   -13 i think we are a match.
•  » » 6 weeks ago, # ^ |   0 It is not a part of competition, if it was, it'd been ended.Anyway, I am curious to know this.