| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1703 | Castle Defend |
|
| 7127 | Slim Span |
|
| 7128 | Dominos |
|
| 7129 | Antenna Placement |
|
| 7130 | Long Distance Taxi |
|
Description
Element TD is a hot game in the world of otaku, and all otakus are crazy about it. According to a CNN report, some friends even quarrel and fight because of the game. It is so terrible! To understand why this game drives people crazy, you decide to play the game now!
Firstly, there are several maps in the game. Each map has a hole that monsters will come out from it unlimitedly. Monsters will only walk along the roads. Each road may contain up to a certain number of monsters. When a monster reaches a road junction, it will choose the next road to walk randomly.
You have a castle to defend from monsters’ attack. To do so, you can build some towers at the road junctions to monitor the road and kill the intruding monsters. Different types of towers have different powers of killing (number of monsters that can be killed in a unit of time) and different building costs. The attack ranges of all the towers are unlimited. For example, for a tower with (power, cost) = (5, 10), then we need to pay 10 dollars to build the tower and this tower can kill 5 monsters in a unit of time.
To be a perfect gamer, you must find the smallest cost for creating enough towers in a given map, such that you can block attacks from the monsters at any time.
Input
The first line contains an integer t (t <= 20) that indicates the number of test cases.
For each test case, the first line contains two integers n (2 <= n <= 70) and m (1 <= m <= n*(n-1)/2), denoting the number of intersections and the number of roads in this map, respectively. The intersections will be labeled by {1, 2, 3, …, n}.
The next m lines are the information of the roads. Each line consists of three integers ei, ej, and cp(i, j). The integers ei and ej indicates that the road is from intersection i to intersection j, and the value cp(i, j) indicates that the road can contain at most cp(i, j) monsters. Each road is directed so that monsters can walk in one direction.
The hole where monsters come out is located at intersection 1, and your castle is located at intersection n. The total number of monsters, which you will kill in a unit of time, will be less than 30,000.
After the road information, the next line will be an integer Q (1 <= Q <= 100), indicating how many types of towers you can choose. And the following Q lines describe the information of each tower. Each line contains two integers pi and gi (1 <= pi, gi <= 1,000), which are the power and the cost of tower i, respectively.
Output
For each case, output a line with the minimum cost for creating enough towers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an undirected weighted graph G , you should find one of spanning trees specified as follows.
The graph G is an ordered pair (V, E) , where V is a set of vertices {v1, v2,..., vn} and E is a set of undirected edges {e1, e2,..., em} . Each edge e belongs to E has its weight w(e) .
A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n - 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n - 1 edges of T .
For example, a graph G in Figure 5(a) has four vertices {v1, v2, v3, v4} and five undirected edges {e1, e2, e3, e4, e5} . The weights of the edges are w(e1) = 3 , w(e2) = 5 , w(e3) = 6 , w(e4) = 6 , w(e5) = 7 as shown in Figure 5(b).
There are several spanning trees for G . Four of them are depicted in Figure 6(a)∼(d). The spanning tree Ta in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree Ta is 4. The slimnesses of spanning trees Tb , Tc and Td shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree Td in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.
Your job is to write a program that computes the smallest slimness.
Input
The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.
n m
a1 b1 w1
.
.
.
am bm wm
Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.
n is the number of the vertices and m the number of the edges. You can assume 2<=n<=100 and 0<=m<=n(n - 1)/2 . ak and bk (k = 1,..., m) are positive integers less than or equal to n , which represent the two vertices vak and vbk connected by the k -th edge ek . wk is a positive integer less than or equal to 10000, which indicates the weight of ek . You can assume that the graph G = (V, E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).
Output
For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, `-1' should be printed. An output should not contain extra characters.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.
Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.
Input
The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.
Output
For each test case, output a line containing one integer, the minimum number of dominos that must be knocked over by hand in order for all the dominos to fall.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.
Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?
Input
On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1<h<40 and 0<w<10. Thereafter is a matrix presented, describing the points of interest in
Output
For each scenario, output the minimum number of antennas necessary to cover all ‘*’-entries in the scenario’s matrix, on a row of its own.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A taxi driver, Nakamura, was so delighted because he got a passenger who wanted to go to a city thousands of kilometers away. However, he had a problem. As you may know, most taxis in Japan run on liquefied petroleum gas (LPG) because it is cheaper than gasoline. There are more than 50,000 gas stations in the country, but less than one percent of them sell LPG. Although the LPG tank of his car was full, the tank capacity is limited and his car runs 10 kilometer per liter, so he may not be able to get to the destination without filling the tank on the way. He knew all the locations of LPG stations.
Your task is to write a program that finds the best way from the current location to the destination without running out of gas.
Input
The input consists of several datasets, and each dataset is in the following format.
N M cap
src dest
c1,1 c1,2 d1
c2,1 c2,2 d2
...
cN,1 cN,2 dN
s1
s2
...
sM
The first line of a dataset contains three integers (N,M,cap), where N is the number of roads (1 <= N <= 3000), M is the number of LPG stations (1 <= M <= 300), and cap is the tank capacity (1 <= cap <= 200) in liter. The next line contains the name of the current city (src) and the name of the destination city (dest). The destination city is always different from the current city.
The following N lines describe roads that connect cities. The road i (1 <= i <= N) connects two different cities ci;1 and ci;2 with an integer distance di (0 < di <= 2000) in kilometer, and he can go from either city to the other. You can assume that no two different roads connect the same pair of cities. The columns are separated by a single space. The next M lines (s1, s2, ... sM) indicate the names of the cities with LPG station. You can assume that a city with LPG station has at least one road.
The name of a city has no more than 15 characters. Only English alphabet (`A' to `Z' and `a' to `z', case sensitive) is allowed for the name.
A line with three zeros terminates the input.
Output
For each dataset, output a line containing the length (in kilometer) of the shortest possible journey from the current city to the destination city. If Nakamura cannot reach the destination, output -1" (without quotation marks). You must not output any other characters.
The actual tank capacity is usually a little bit larger than that on the specification sheet, so you can assume that he can reach a city even when the remaining amount of the gas becomes exactly zero. In addition, you can always fill the tank at the destination so you do not have to worry about the return trip.