## DMPG '19 G5 - Hunting the White Whale

View as PDF

Points: 25 (partial)
Time limit: 4.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Rem notices that the white whale also travels along these roads; specifically it continually travels along a single path that sees a total of travelers per day. 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.

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