## DMPG '19 G5 - Hunting the White Whale

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Subaru and Rem are hunting down the white whale. They currently have a list of locations where the white whale has been rumoured to appear. There are roads that connect every location to every other location. The th of these typically sees travelers per day.

If the white whale travels along these roads, it continually travels along a single path that sees a total of travelers per day, picked uniformly at random from all such paths. Doing so means that it will pass all locations that are on this path. Thus Rem asks Subaru questions: if we wait at node , what is the probability we will encounter the whale?

#### Constraints

The network of roads forms the simplest possible line: For , road connects locations and .

#### Input Specification

The first line of input will contain two space-separated integers, and .
The next lines will each contain 3 integers: , indicating there is an road between locations and , with travelers per day.

#### Output Specification

You should output lines, where each is the probability Rem and Subaru encounter the white whale, expressed as a fraction in lowest terms.

#### Sample Input

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

#### Sample Output

1 / 3
1 / 3
1 / 1
1 / 1
1 / 3

#### Explanation for Sample Output

The possible paths are:

Locations and appear on all paths, but locations , , and only appear on a single path each.

• commented on Nov. 1, 2020, 9:01 p.m. edit 3

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Aug. 13, 2020, 10:51 a.m. edited

edit: nvm

• commented on June 9, 2019, 12:07 a.m.

what if a path has no chance? should it be 0 / 1?

• commented on June 9, 2019, 12:09 a.m.

is a fraction in lowest terms