Perpetuum Mobile
Time limit2sMemory limit512 MB
Given a directed graph with positive decimal arc weights, decide whether it contains a cycle whose product of edge weights is at least 1 (detecting energy amplification).
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Math, Implementation
- Solved
- No attempts yet
Problem
The year is 1902. Albert Einstein works at the patent office in Bern. Many patent proposals contain egregious errors; some even violate the law of conservation of energy. Worse still, most proposals use non-standard physical units that are not part of the metric system, or are not even documented. Every proposal has the following form:
- Every patent proposal contains n energy converters.
- Every converter has an unknown input energy unit associated with it.
- Some energy converters can be connected: if converter a can be connected to converter b so that one energy unit associated with a turns into c input units for b, the proposal shows this as an arc a → b (c). The output of a can be used as input for b if and only if such an arc from a to b exists.
Einstein wants to reject outright every proposal in which the energy converters can be chained into a cycle that feeds more energy back into a converter than was given to it as input, violating the law of conservation of energy.
Einstein's assistants know that he was born for greater things than weeding out faulty patent proposals. So they handle the hardest cases, and the proposals given to Einstein are of a rather restricted form. Every admissible patent proposal given to Einstein has no cycle whose total product of arc weights exceeds 0.9. By contrast, every inadmissible patent proposal given to Einstein contains a cycle whose number of arcs does not exceed the number of converters defined in the proposal, and whose total product of arc weights is at least 1.1.
Can you help Einstein identify the inadmissible proposals?
Input
The input consists of:
-
one line with two integers n and m, where
- n (2 ≤ n ≤ 800) is the number of energy converters;
- m (0 ≤ m ≤ 4000) is the number of arcs.
-
m lines each containing three numbers ai, bi, and ci, where
- ai and bi (1 ≤ ai, bi ≤ n) are integers identifying energy converters;
- ci (0 < ci ≤ 5.0) is a decimal number indicating that converter ai can be connected to converter bi so that one input unit associated with ai is converted to ci units associated with bi. The number ci may have up to 4 decimal places.
Output
Output a single line containing inadmissible if the proposal given to Einstein is inadmissible, admissible otherwise.