Solve using Dijkstra.
Outbreak! Buried deep in the heart of the CDC (Center for Disease Control) is a laboratory. In this laboratory there are many animals housed in cages. Each cage contains one animal. One day, at 8am, because of a terrible mixup with the animal feed, some of the animals are exposed to and become infected with a deadly virus. An animal, once infected with the virus, will eventually become contagious and later die. Once an animal becomes contagious, it will immediately infect the animals in the cages adjacent to its own cage. More specifically, an animal v will become contagious Cu time units after it becomes infected (the amount of time depends on the animal), and it will die Dy time units after it becomes infected you may assume that D C) The question is: which animals will eventually die, and at what time will they drop dead? You are to design an efficient algorithm to answer this question. Assume the animals are numbered 1,., n. As inputs, you are given, for each animal v e (1,.n: the values Cy and Dy (which are positive numbers); a list of all animals that are in cages adjacent to v's cage You are also given the set S {1, ,n} of initially infected animals. You should also assume that each cage is adjacent to at most 8 other cages. Your algorithm should run in time O(n log n). Hint: solve this by reduction to a standard single-source shortest path problem on a directed graph. Disclaimer: no animals were harmed in the production of this exercise. Outbreak! Buried deep in the heart of the CDC (Center for Disease Control) is a laboratory. In this laboratory there are many animals housed in cages. Each cage contains one animal. One day, at 8am, because of a terrible mixup with the animal feed, some of the animals are exposed to and become infected with a deadly virus. An animal, once infected with the virus, will eventually become contagious and later die. Once an animal becomes contagious, it will immediately infect the animals in the cages adjacent to its own cage. More specifically, an animal v will become contagious Cu time units after it becomes infected (the amount of time depends on the animal), and it will die Dy time units after it becomes infected you may assume that D C) The question is: which animals will eventually die, and at what time will they drop dead? You are to design an efficient algorithm to answer this question. Assume the animals are numbered 1,., n. As inputs, you are given, for each animal v e (1,.n: the values Cy and Dy (which are positive numbers); a list of all animals that are in cages adjacent to v's cage You are also given the set S {1, ,n} of initially infected animals. You should also assume that each cage is adjacent to at most 8 other cages. Your algorithm should run in time O(n log n). Hint: solve this by reduction to a standard single-source shortest path problem on a directed graph. Disclaimer: no animals were harmed in the production of this exercise
