|Online Judge||Problem Set||Authors||Online Contests||User|
There is a lot of caves in Byteland. This is the map of one of them:
All caves in Byteland have the following properties:
It is possible to walk from one chamber to another using only inner passages but there is only one way to do that if we allow to walk through every inner passage at most once.
Not all passages are equally hard to go through. They are divided into two groups: easy and hard.
It has been decided to open all the caves to the public. To assure a "smooth" and safe flow through a cave, visitors should follow a route marked in advance and visit every chamber of this cave exactly once. An exception from this rule is the entrance chamber where every tour begins and ends, you are allowed to visit this chamber exactly twice. The tour route should be fit for an average visitor and contain as few hard passages to walk through as possible.
Consider the cave showed in the figure. The entrance chamber is 1. The dashed passages are hard to walk through. Route 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all. The final chamber, number 1, is implied and not listed.
Write a program that:
There are two integers n, k (separated by a single space) in the first line The integer n, 3 < n <= 500, is the number of all chambers in a cave and k is the number of all its outer chambers, k >= 3. The chambers are numbered from 1 to n. Chamber 1 is the entrance chamber. Chambers 1, 2, ..., k are outer chambers. They do not have to appear on the outer circle in this order.
The next 3n / 2 lines contain descriptions of the passages. Each description consists of three integers a, b, c separated by single spaces. The integers a and b are numbers of chambers at the ends of a passage. The integer c equals 0 or 1, where 0 means that the passage is easy to walk through and 1 that it is hard.
Your program should write a sequence of n integers separated by single spaces to the first line of the standard output; the sequence has to begin with 1 (the entrance chamber). The following n - 1 integers should be consecutive chambers on the computed route.
8 5 1 3 0 3 2 0 7 3 1 7 2 0 8 7 0 1 8 0 6 8 0 6 4 0 6 5 1 5 4 0 2 4 0 5 1 0
1 5 4 6 8 7 2 3
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator