Want to try solving this problem? You can submit your code online if you log in or register.

Vlad and Tony work in different parts of the city but they enjoy walking home together.

The city can be thought of as a weighted undirected graph, where the N intersections are vertices and the M two-way roads (each with their own lengths) are edges. Intersections are numbered 1 to N. Vlad's office is at intersection 1, Tony's office is at intersection 2, and their house is at intersection N.

Every day, Vlad and Tony both leave work at the same time, walking at the same speed. Each of them takes a shortest path to their house, so that they arrive at the house as early as possible. There may be more than one shortest path from Vlad's office to their house. (Two Vlad-shortest-paths are considered different if they do not visit the same sequence of intersections.) Likewise, there may be more than one shortest path from Tony's office to their house.

Whenever Vlad and Tony walk along the exact same road in the same direction, starting and finishing at the same times, we say they spend quality time together. Vlad and Tony would like to spend as much quality time together as possible.

Your task is to determine how much quality time Vlad and Tony can spend together as they walk home. In addition, you should also determine how many different combinations of Vlad-shortest-paths and Tony-shortest-paths achieve this maximum amount of quality time. This number should be given modulo 1,000,000,007.

The first line of input will consist of N and M separated by a space. Each
of the following M lines describes a single road and is given in the form
"a_{i}b_{i}t_{i}", representing a road connecting intersection a_{i} to
intersection b_{i} which takes t_{i} minutes to travel along.

Each pair of intersections will be connected by at most one road. No road will connect an intersection to itself. You are guaranteed that there is a path from both intersections 1 and 2 to intersection N, i.e. it is possible for both Vlad and Tony to go home.

The first line of output should consist of a single integer: the maximum amount of quality time Vlad and Tony can spend together as they walk home, given in minutes.

The second line of output should consist of a single integer: the number of different combinations of Vlad-shortest-paths and Tony-shortest-paths that achieve this maximum amount of quality time, modulo 1,000,000,007.

7 10 1 4 5 2 3 2 3 4 3 3 5 4 2 4 5 4 5 1 4 6 2 5 6 1 5 7 2 6 7 1

3 6

4 5 1 3 2 1 4 3 2 3 2 2 4 3 3 4 2

0 1

In the first example, Vlad and Tony can spend 3 minutes of quality time together by meeting at intersection 4. Combinations of Vlad-shortest-paths and Tony-shortest-paths that result in maximum quality time together are:

Notice that although Vlad could take the shortest path 2 -> 3 -> 5 -> 7 home, this would not allow him to spend as much time with Tony.

In the second example, Tony and Vlad may not meet up at intersection 3 and walk together, because this would require them not to take shortest paths home. Instead, they must both take their unique shortest path home, spending zero quality time together.

5 5 1 2 1 2 3 1 2 4 1 3 5 1 4 5 1

0 4

13 19 1 3 1 1 4 1 3 5 1 4 5 1 1 6 2 2 7 1 2 8 1 7 5 1 5 8 1 2 6 2 5 9 1 5 10 1 6 11 1 6 12 1 9 13 1 10 13 1 11 13 1 12 13 1 6 13 2

2 11

In the third example, Tony starts closer to home than Vlad. Since they must both leave at the same time and take shortest paths, Tony cannot "wait up" for Vlad and instead they spend zero quality time together.

Combinations of Vlad-shortest-paths and Tony-shortest-paths that result in maximum quality time together are:

Vlad |
Tony |
---|---|

1 -> 2 -> 3 -> 5 | 2 -> 3 -> 5 |

1 -> 2 -> 3 -> 5 | 2 -> 4 -> 5 |

1 -> 2 -> 4 -> 5 | 2 -> 3 -> 5 |

1 -> 2 -> 4 -> 5 | 2 -> 4 -> 5 |

In the fourth example, there are eleven paths allowing Vlad and Tony to achieve two minutes of quality time together.

For all subtasks, 1 ≤ N ≤ 100,000 and 1 ≤ M ≤ 100,000.
All t_{i} satisfy 1 ≤ t_{i} ≤ 10,000.

- For Subtask 1 (20 points), there are no cycles and every intersection is
reachable from every other intersection.
- For Subtask 2 (25 points), all t
_{i}= 1. - For Subtask 3 (30 points), 1 ≤ N ≤ 1,000.
- For Subtask 4 (25 points), no further constraints apply.

Your score for each test case will be 100% if both lines are correct, 50% if exactly one is correct, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:08am AEDT