|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||455||84||62||21.678%|
Ancient history and myth points to the Gunung Ledang (a.k.a. Ledang Mountain, as “gunung” is mountain in Malaysian) being the site of rich gold deposits, luring traders from as far as Greece and China. In the 14th Century, the Chinese seafarers plying the Straits of Melaka called it ‘Kim Sua’ meaning the ‘Golden Mountain’. The mountain was named ‘Gunung Ledang’, which means ‘mount from afar’, during the period of the Majapahit empire. Legend has it, that before the death of Princess Gunung Ledang, she hid a huge amount of gold far back in time during the creation of earth in Ledang Mountain. It is(apparently, becoming “was”) a mystery as to how the princess was able to go so far back in time. However, the princess was known to possess mystical powers that could enchant any pool she bath in into a portal that could manipulate time and space. A Malaysian historian of this time have discovered many of these pools located near many mountains around the world and named them “Ledang Pools”. A Ledang Pool is a portal through space and time connecting two pools. Ledang Pools have a few peculiar properties:
The Malaysian historian suspects that a large amount of gold is hidden in Ledang Mountain in the past because there’s no gold found in this mountain at this time (but then, where does the myth come from?). Starting from Ledang Mountain, the historian wants to reach the same mountain (Ledang Mountain) in the past. In order to this, he has to hop into two or more Ledang Pools, doing the space-and-time-travel things, and end up at Ledang Mountain in the past. Note that he does not care in which time in the past he will end up at Ledang Mountain as long as it is in the past. Your task is to help this historian to determine whether it is possible to reach Ledang Mountain in the past from Ledang Mountain in the present time by hopping a sequence of Ledang Pools.
The input file starts with a line containing the number of cases T (1 ≤ T ≤ 20). Each case starts with two numbers N and M in a line. These indicate the number of mountains which have Ledang Pool end point (1 ≤ N ≤ 1,000) and the number of Ledang Pools (0 ≤ M ≤ 2,000). The pools are numbered from 0 (Ledang Mountain in Malaysia) up to N-1. The next M lines each contains three integers A, B, C (0 ≤ A, B < N; A ≠ B; -1,000 ≤ C ≤ 1,000) denoting the properties of one Ledang Pool, i.e. someone can do a space-time-travel from mountain A to mountain B and he will end up C year in the future/past. If C is positive, then it is in the future, otherwise it is in the past.
For each case, output in a line "Case #X: Y" (without quotes) where X is the case number starting from 1, and Y is “possible” (without quotes) if it is indeed possible to reach Ledang Mountain in the past, otherwise output Y as “not possible” (without quotes).
2 2 2 0 1 15 1 0 -20 4 4 0 1 10 1 2 20 2 3 30 3 0 -60
Case #1: possible Case #2: not possible