TopCoder SRM 584 - 900: FoxTheLinguist

Problem Statement

有 N 门课,每门课有 Level 0 ~ Level 9,
一开始你会每门课的 0 级,有 M 种训练,
每种训练可以描述为 “在你学会了 A 的 Level B 之后,可以花 T 的时间学会 C 的 Level D”,
当然,当你某门课学会了某个等级,那么这门课之前的等级都可以视为学会,
问所有课到达 9 级的最短时间,或说明不可能.

N <= 9
M <= 200

Fox Ciel plans to learn n new foreign languages because she is such a clever fox. The languages are named with characters 'A', 'B', ..., 'A'+n-1. For each language, there are ten levels of fluency from 0 to 9. Fox Ciel starts out with fluency 0 in every foreign language. Level 9 denotes mastery of the language.

A number of language courses are available to Fox Ciel. Each course has a prerequisite language and level, and it leads to a target language and level. The prerequisite language is not necessarily the same as the target language. Each course also takes a certain amount of time.

A course is described by the String[] courseInfo. Concatenate all of the Strings to obtain a single String that looks like this:

"B9->C2:0200 A0->A9:1000 A3->A4:0001"

Note that the number after the colon (':') is always four digits long. The example above contains three courses. The first one is described as "B9->C2:0200", which means that if Fox Ciel has achieved a fluency of no less than 9 in language B, she can spend 200 hours in this course to achieve a fluency of exactly 2 in language C.

How much time must Fox Ciel spend to master (i.e., reach level 9 in) every language? Return the minimal number of hours, or return -1 if it is not possible for her to master every language.

Test cases

input
- n 1
- courseInfo { "A0->A9:1000 A0->A6:0300 A3->A9:0600" }
output
Returns 900

note

There are three courses and one foreign language. Fox Ciel could spend 1000 hours on the first course to master the language. The optimal solution is to take the second course, followed by the third course, for a total expenditure of 300 + 600 = 900 hours.
input
- n 2
- courseInfo { "A0->A9:1000 B0->B9:1000 A1->B9:0300 B1->A9:0200" }
output
Returns 1200

note

The optimal solution is to take the second course to master language B, then the fourth course to master language A.
input
- n 3
- courseInfo { "C0->A6:00", "01 A3", "->B9:0001 A3->C6:000", "1", " C3->A9:0001 A9->C9:0001 A0->A9:9999", " B0->B9:9999 C0->C9:9999 A6->A9:9999" }
output
Returns 5
input
- n 4
- courseInfo { "A0->A6:6666 A0->A9:9999", " B0->B6:6666 B0->B9:9999", " C0->C6:6666 C0->C9:9999", " D0->D6:6666 D0->D9:9999", " A6->B6:0666 B6->C6:0666", " C6->D6:0666 D6->A6:0666", " A9->B9:0099 B9->C9:0099", " C9->D9:0099 D9->A9:0099" }
output
Returns 10296
input
- n 1
- courseInfo { "A0->A9:9999 A0->A9:8888" }
output
Returns 8888

note

It is possible for several courses to have the same prerequisite and target.
input
- n 1
- courseInfo { "A9->A9:0000", " A9->A0:0000" }
output
Returns -1

back to the menu

SRM 584 1 900 FoxTheLinguist

Problem Statement

Definition

Limits

Constraints

Test cases