CommonLounge Archive

[UVA 11721] Instant View Of Big Bang

May 27, 2017

Problem in Short:

There are N star systems in the space, connected by M wormholes. Each wormhole can teleport you from a system A to system B (you cannot teleport in the opposite direction).

Each wormhole has a fixed time shift T (negative or positive). If it’s positive it will take you from system A to system B and you will land T years after. If T is negative, it will take you from A to B and land T years before (in the past).

You are asked to determine the star systems such that for each of them, you can start a journey there and keep traveling in the past (via wormholes) infinitely, so you can watch the Big Bang :)

Constraints: N <= 1000, M <= 2000

© 2016-2022. All rights reserved.