Problem Statement |
| | A network consists of routers and links. Each link directly connects two routers. Links can transfer
data in both directions, and have unlimited bandwidth but limited transfer speed. We know how many time
units it takes for each link to transmit a packet from one end to the other.
The routers know the layout of the network and relay data packets so that the packet reaches its
destination in the shortest possible time. Suppose a router wants to send a packet to some other
router. The source router will calculate the shortest path to the destination router and send the
packet to the first router on that path. That router will then proceed in the same way, and so on
until the packet reaches its destination. If a router can send to more than one neighboring router and
have the packet delivered in the same minimal time, it will send to the lowest-numbered of those routers.
When a link fails, the two routers it connected know about it immediately, but the other routers do not.
The two routers generate control packets containing information about the failed link
and distribute the control packets to all their immediate neighbors (over links that haven't failed themselves). When a router receives a
control packet, it updates its internal layout of the network and passes copies of the control
packet to its neighbors.
If a router receives more than one packet at the same time, it will analyze all the incoming
packets before generating any outgoing traffic.
At time index 0, a number of links failed and a single data packet was sent from router
A to router B. You are given the initial layout of the network as a String[],
the list of failed links as a int[] and the integers A and B.
The routers are labelled with integers between 1 and 99. Links in
layout will be formatted as "ROUTER1 ROUTER2 TIME", meaning that the link connects routers labelled
ROUTER1 and ROUTER2 and it takes TIME time units for packets to be sent over it. A value of x in failed
means that the link described by element x of layout has failed (index is 0-based).
Return an int, the number of time units needed for the data
packet to reach router B. If the packet can never reach the destination, return -1.
|
| |
Definition |
| | | Class: | AdaptiveRouting | | Method: | deliveryTime | | Parameters: | String[], int[], int, int | | Returns: | int | | Method signature: | int deliveryTime(String[] layout, int[] failed, int A, int B) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | There can be more than one link connecting two routers. |
| |
Constraints |
| - | layout will contain between 0 and 50 elements, inclusive. |
| - | Each element of layout will be formatted as "ROUTER1 ROUTER2 TIME" (quotes for clarity). |
| - | ROUTER1 and ROUTER2 in each element of layout will be distinct integers between 1 and 99, inclusive, without leading zeroes. |
| - | TIME in each element of layout will be an integer between 1 and 10^7, inclusive, without leading zeroes. |
| - | Each element of failed will be between 0 and n-1, inclusive, where n is the number of elements in layout. |
| - | failed will not contain duplicate elements. |
| - | A and B will be between 1 and 99, inclusive. |
| - | A and B will be different. |
| |
Examples |
| 0) | |
| | { "1 2 1", "2 3 1", "2 5 1", "3 4 1", "4 6 1", "5 6 1" } | { } | 1 | 6 |
| Returns: 3 | | With no failed links, the packet gets sent by the shortest route (1 -> 2 -> 5 -> 6). |
|
|
| 1) | |
| | { "1 2 1", "2 3 1", "2 5 1", "3 4 1", "4 6 1", "5 6 1" } | { 5 } | 1 | 6 |
| Returns: 4 | | The link between routers 5 and 6 has failed. After 1 time unit, the data packet gets to router 2. At that same moment word of the failed link gets to router 2 from router 5, so router 2 sends the packet through routers 3 and 4. |
|
|
| 2) | |
| | { "1 2 1", "1 2 22" } | { 0 } | 1 | 2 |
| Returns: 22 | | The primary link has failed so the packet is sent through the auxiliary (slow) link. |
|
|
| 3) | |
| | { "4 3 100", "2 4 3", "3 2 1", "2 5 1", "4 1 2", "5 4 1" } | { 2, 5 } | 1 | 3 |
| Returns: 108 | |
|
| 4) | |
| | { "10 12 5", "10 11 2", "11 12 3" } | { 2 } | 10 | 12 |
| Returns: 9 | |
|
| 5) | |
| | { "53 21 6", "53 21 4", "9 85 4", "9 90 7", "53 90 1",
"21 9 7", "85 7 5", "90 47 7", "85 9 3", "53 85 5",
"7 47 9", "53 7 9", "7 47 1", "21 47 6", "90 47 2" }
| { 14, 9, 7, 8, 0, 3 } | 53 | 47 |
| Returns: 12 | |
|
| 6) | |
| | { "65 37 24", "37 2 66", "65 37 32", "65 46 97",
"65 3 52", "37 3 66", "65 77 50", "3 56 99",
"77 3 100", "3 2 39", "46 3 75", "56 46 79",
"46 2 83", "3 77 73", "3 2 60", "77 2 90" } | { 10, 4, 0, 3, 8, 15, 12, 1, 13, 9, 7, 2 } | 65 | 2 |
| Returns: -1 | |
|