One of the well-known ability of the naga siren is that she could create multiple illusions of herself under her command, that is, she splits herself into numerous replicates of herself which acts according to her will. However to create illusions she needs mana (magic power) supply, which will obly be available at certain arcane locations with magic power emerging.
On a bright day of August the naga siren decides to set out for an adventure to explore the ancient regions of Dota Kingdom. The Dota Kingdom can be described by a weighted directed graph, each node represents either a sacred place with mana supply (so the naga could create arbitrary number of mirror images) or a regular location (just ordinary places so the naga cannot split herself into replicates at the locations), and each weighted directed edge represents a single-way road leading from a place to another.
Now the naga wishes to explore "every sacred places" in Dota Kingdom. Given the map of Dota Kingdom, assume that initially the naga begins at node 0, determine the least amount of distance the naga has to travel in order to reach all the sacred places. The total distance traveled is defined by "the sum of all the distances traveled by the naga siren herself and all her illusions". That is, for example, the naga walked a distance of 1 and splits into two, then each two of her (either illusion or herself) traveled a distance of 2 and 4, respectively. Then, the total distance traveled is 1+2+4 = 7.
The input file may contain several instance of input data, and is terminated by EOF.
Each instance of input is first described by 3 integers N, M, K, where N is the number of distinct locations in Dota Kingdom numbered from 0 (the start) to N-1, K is the number of sacred places which is labeled from 0 to K-1, and M is the number of directed roads. Following is M lines each with 3 integers V, U, L, denoting there's a road from location V to location U of length L. There COULD BE multiple roads between the same pair of nodes, but there WILL NOT BE self-loop.
For each input testcase, output a line with a single integer: the minimum distance the naga has to travel to explore all the sacred places. If it is impossible to explore all sacred area, output a line containing only "sad.."
7 9 5 1 0 1 0 5 3 0 3 5 2 1 4 5 2 1 3 2 2 3 6 3 6 4 2 2 4 6 2 1 2 1 0 10
16 sad..
Migrated from old NTUJ.
kelvin. Reference: dmst and uva 10307
| No. | Testdata Range | Score |
|---|