SRM 492 div1 level 2

There is a kingdom with N cities numbered 0 through N-1. Gogo wants to survey several cities in the kingdom. These cities are described in int[] cities containing M elements. He wishes to survey city cities[0], city cities[1], ..., city cities[M-1] in this exact order (i.e., before surveying city cities[i], he must have finished surveying cities cities[0], ..., cities[i-1] in this order). He starts at city 0 and can end at any city. He may only survey a city when he's inside the city. There are several bidirectional roads, each connecting two different cities and costing some amount of money to traverse. Note that he may wish to survey the same city multiple times.



Gogo also has a time machine. He can use the time machine to go back in time, without affecting which cities he is considered to have already surveyed. For example, suppose he has visited cities A, B, C, D, and E, in that order, and is currently in city E. He can use the time machine to go back to city A, B, C, or D. Suppose he chooses to go back to city C. At that point, he can then go back further to city A or B, but he cannot use the time machine to go forward to city D or E. Note that if he had surveyed city E, going back in time will not change the fact that he is considered to have already surveyed city E.



You are given the roads in the String[] roads. Concatenate the elements of roads, in order, to get a single space-separated list of roads. Each road will be formatted "a,b,travelcost" (quotes for clarity), which means that the bidirectional road connects city a and city b, and costs travelcost to traverse.



He can use the time machine any number of times, and it costs nothing to use it. Return the minimum cost required to survey all cities from cities in the given order. Return -1 if it is impossible to survey them all.

Definition

Class:	TimeTravellingTour
Method:	determineCost
Parameters:	int, int[], String[]
Returns:	long
Method signature:	long determineCost(int N, int[] cities, String[] roads)
(be sure your method is public)

Notes

-

Surveying a city does not incur any cost.

Constraints

-

N will be between 2 and 50, inclusive.

-

cities will contain between 1 and 50 elements, inclusive.

-

Each element of cities will be between 0 and N-1, inclusive.

-

No two consecutive elements in cities will be identical.

-

cities[0] will not be 0.

-

roads will contain between 1 and 50 elements, inclusive.

-

Each element of roads will contain between 1 and 50 characters, inclusive.

-

Each character in roads will be '0'-'9', ' ', or ','.

-

roads will be formatted as described in the problem statement without leading or trailing spaces.

-

All integers in the concatenation of all the elements of roads in the order they are given will have no leading zeroes.

-

In each road, a and b as described in the problem statement will be different and will each be between 0 and N-1, inclusive.

-

In each road, travelcost as described in the problem statement will be between 1 and 10,000,000, inclusive.

-

For each two different cities, there will be at most one road connecting them.

Examples

0)

5

{2,3,2,4}

{"0,2,4 0,1,2 2,1,2 1,3,3 4,0,4"}

Returns: 13

Travel from city 0 to city 1 to city 2. Survey city 2. Go back in time to city 1. Travel from city 1 to city 3. Survey city 3. Go back in time to city 1. Travel from city 1 to city 2. Survey city 2. Go back in time to city 0. Travel from city 0 to city 4. Survey city 4. The total cost is 2+2+3+2+4=13.

1)

3

{1,0,1}

{"0,2,1"," 2",",1,5"}

Returns: 12

Travel from city 0 to city 2 to city 1. Survey city 1. Go back in time to city 0. Survey city 0. Travel from city 0 to city 2 to city 1. Survey city 1.

2)

3

{2}

{"0,1,2"}

Returns: -1

It is not possible to reach city 2.

3)

6

{4, 1, 3, 2}

{"0,1,5 0,2,5 0,5,2 2,3,5 2,4,2 3,4,4 3,5,1"}

Returns: 19

Travel from city 0 to city 2 to city 4. Survey city 4. Travel from city 4 to city 3 to city 5 to city 0 to city 1. Survey city 1. Go back in time to city 3. Survey city 3. Go back in time to city 2. Survey city 2. The total cost is 5+2+4+1+2+5=19

【题解】

此题很难，自己一时说不清楚。

官方题解：

So, first, we are at city 0, we need to survey cities[0]..cities[M-1]. Can we actually represent this as our state? I.e, a triple (C,u,v) which means that we're at city C and need to survey cities[u]..cities[v]? Let's investigate!

So what happens now is that we move to another city, suppose city D. So now, we're at city D, we need to survey cities[0]..cities[M-1]. If cities[0] is city D, then we survey the city and update into cities[1]..cities[M-1]. However, if we represent this as triple (D,u,v), we lose the fact that we can travel back in time to city C. So it appears that we can't forget about city C. But there lies the key to the problem.

Suppose we travel back in time to city C. Can we now forget about city D? We can, since we can't reverse back to city D and so aside from its effect on u and v, it leaves no other trace.

Let's revisit the triple (D,u,v). If we will never reverse back in time to city C, then this triple will be sufficient. Otherwise, we will at some time reverse back to city C. The question is when? We will need to travel back in time to city C because we want to survey some city cities[i] in cities[u]..cities[v]. So the idea is that we will at some point reverse the time back to city C to survey some cities[i]..[v] (to v because once we go back in time, we effectively forget about D and all cities we traversed afterwards). This also implies that during our trip to survey cities[u]..cities[i-1], we will never return back in time to city C (Except if we revisit city C through 'traversing' and not 'going back in time' - but in this case we will ultimately be able to travel back in time to city C that we first visit). Hey, now we seem to have a solid ground to step on!

Indeed, during our trip to visit cities[u]..cities[i-1], the fact that we will never return back in time to city C enables us to forget city C during that course, i.e., it can be conveniently represented by the tuple (D,u,i-1). And then, since we will never travel back in time when we're already at city C, we can also represent the other part as a tuple (C,i,v) (since we won't need to remember D).

So what's the conclusion of our discussion so far? We can represent our state as a triple (C,u,v), and we can solve a triple by breaking it into two other triples. Now, we if we treat each triple like how we treat the triple above, then we get a recursive solution!

Solution the First

So, how do we solve a triple (C,u,v)? In other word, what should a triple return? Well, let's define the triple again.

(C,u,v) is the minimum cost required such that we're now at city C, we're not allowed to go back in timefurther than this city, and we need to survey cities[u]..cities[v].

And now, the recursion will be presented in a pseudocode

//#PART 1#
if (u > v) {
	//basis step, we have finished surveying all required cities
	return 0;
}
if (cities[u] == C) {
	//we survey city C
	return (C, u+1, v);
}

answer = huge number;


for each city D {
	for i = u to v {
		//we go to city D, and we'll return to C at i
		answer = min(answer, (D, u, i-1) + (C, i, v) + dist[C][D])
	}
}
//#END OF PART 3#
return answer;