algorithms hw5*

Encerrado Postado Dec 17, 2003 Pago na entrega
Encerrado Pago na entrega

**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 *[url removed, login to view]* 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 *[url removed, login to view]*. The first line of [url removed, login to view] 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 *[url removed, login to view]*).

## 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

time limit:max 5 seconds with pII-450

Programação C Engenharia Linux MySQL PHP Arquitetura de software Teste de Software

ID do Projeto: #3047215

Sobre o projeto

15 propostas Projeto remoto Ativo em Dec 24, 2003

15 freelancers estão ofertando em média $20 nesse trabalho

abstractvision

See private message.

$10.2 USD in 2 dias
(141 Comentários)
6.1
codexvw

See private message.

$5.95 USD in 2 dias
(50 Comentários)
6.0
zeegaal

See private message.

$11.05 USD in 2 dias
(59 Comentários)
5.1
andrewlazarev

See private message.

$12.75 USD in 2 dias
(12 Comentários)
3.6
maxtabachuk

See private message.

$84.15 USD in 2 dias
(4 Comentários)
3.2
malis

See private message.

$29.75 USD in 2 dias
(6 Comentários)
2.8
ussrvw

See private message.

$21.25 USD in 2 dias
(14 Comentários)
2.2
tymek

See private message.

$11.05 USD in 2 dias
(7 Comentários)
2.2
adrianhara

See private message.

$17 USD in 2 dias
(7 Comentários)
1.9
vs1984

See private message.

$8.5 USD in 2 dias
(5 Comentários)
0.4
hagteam

See private message.

$12.75 USD in 2 dias
(1 Comentário)
0.5
jbhaskar

See private message.

$7.65 USD in 2 dias
(0 Comentários)
0.0
bestdevelopervw

See private message.

$34 USD in 2 dias
(0 Comentários)
0.0
hadezvw

See private message.

$21.25 USD in 2 dias
(0 Comentários)
0.0
dmitryandrusenko

See private message.

$12.75 USD in 2 dias
(1 Comentário)
0.0