algorithms hw5

**ACME Times** * * *ACME press has two printing houses (denoted by -1 and -2) located at different geographic locations . Every day n/2 trucks depart from each printing house to distribute ACME Times, the most respectable newspaper in the country, to n neighbouring cities (n=2*k, 1<k<=30). Cities are denoted by numbers between 1 and n. All n cities must receive ACME Times and a truck can not distribute its load to more than one city. Due to economic crisis, ACME press management wants to lower distribution costs by decreasing total distance traveled by trucks. You are given the length of roads connecting cities and printing houses, and your task is to help them by writing a program that finds which truck must distribute to which city in order to minimize total distance traveled by trucks. **Input** The first line of the input file *[login to view URL]* contains two integers n and m denoting the number of cities and number of roads respectively. Each of the following m lines contains three numbers ui, vi and di (0 < di <= 1000) which states that city (or printing house) ui is connected to city (or printing house) vi by a road of length di. All roads are bidirectional. You can assume that the input is error-free. _newspaper.inp_ 4 7 -1 3 7 -1 4 3 -2 1 6 -2 3 13 1 3 5 3 4 3 2 3 7 ![][1] **Output** Output of your program is a file named *[login to view URL]*. The first line of [login to view URL] must contain a single integer number, giving the minimum possible total distance traveled by trucks. The second and third lines must contain n/2 integer numbers seperated by a blank, giving the numbers of cities visited by trucks starting from printing house -1 and -2 respectively. _newspaper.out_ 33 3 4 1 2 **Submission** You will submit your source file *newspaper.c* (or *[login to view URL]*). ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site). ## Platform Linux must run in less than 5seconds on a PII-450