A Path Problem 2

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Given a bidirectional weighted graph of nodes and edges, print the length of the shortest path from to , as well as the number of such shortest paths.

A shortest path is different from another shortest path if the edges of the path differ by at least one edge.

Input Specification

The first line will four integers, .

The next lines will each contain three integers, . It is guaranteed there are no self loops or duplicate edges. It is also guaranteed the entire graph is connected.

Output Specification

On the first line, output the length of the shortest path.

On the second line, output the number of such shortest paths.

Sample Input 1

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

Sample Output 1

3
2