python zombie smash solution

zombiesmash.py

import sys

def prepare_input():
    num_cases = int(sys.stdin.readline())
    for case_i in xrange(num_cases):
        num_zombies = int(sys.stdin.readline())

        zombies = []

        for zombie_i in xrange(num_zombies):
            x, y, time = sys.stdin.readline().strip().split()
            zombies.append({
                'x': int(x),
                'y': int(y),
                'spawn_time': int(time),
            })

        print 'Case #{0}: {1}'.format(case_i + 1, solve_case(zombies))


def solve_case(zombies):
    distances = []
    for zombie in zombies:
        travel_time = distance(zombie['x'], zombie['y'], 0, 0) * 100
        if travel_time <= zombie['spawn_time'] + 1000:
            distances.append(
                max(zombie['spawn_time'], travel_time)
            )
        else:
            distances.append(False)

    smashes = 0
    while paths_remain(distances):
        smashes += 1
        new_distances = [False] * len(zombies)
        for i, zombie_a in enumerate(zombies):
            for j, zombie_b in enumerate(zombies):
                if i != j and distances[j] is not False:
                    new_distance = distances[j] + max(750, 100 * distance(
                        zombie_a['x'],
                        zombie_a['y'],
                        zombie_b['x'],
                        zombie_b['y']
                    ))

                    if new_distance <= zombie_a['spawn_time'] + 1000:
                        if new_distances[i] is not False:
                            new_distances[i] = min(
                                new_distances[i],
                                max(new_distance, zombie_a['spawn_time'])
                            )
                        else:
                            new_distances[i] = max(new_distance, zombie_a['spawn_time'])

        distances = new_distances
    return smashes


def paths_remain(distances):
    for v in distances:
        if v is not False:
            return True
    return False


def distance(xa, ya, xb, yb):
    return max(abs(xa - xb), abs(ya - yb))

if __name__ == "__main__":
    prepare_input();

# real 0m12.741s
# user 0m12.732s
# sys  0m0.013s