Форум программистов, компьютерный форум CyberForum.ru

графы - C++

Восстановить пароль Регистрация
 
blanc_miami
0 / 0 / 0
Регистрация: 17.11.2011
Сообщений: 16
12.05.2012, 18:05     графы #1
Условие
Вводится число N – количество домиков и число К – количество дорог. Домики пронумерованы числами от 1 до N. Каждая дорога определяется тройкой чисел: двумя номерами домиков, которые являются концами этой дороги, и длиной дороги (длины дорог - положительные целые числа). В каждом домике живет по одному человеку.

Необходимо найти точку (место встречи всех людей), от которой суммарное расстояние до всех домиков будет минимальным. Если точка лежит на дороге, то указать номера домиков, которые являются концами этой дороги, и расстояние от первого из этих домиков. Если точка совпадает с домиком, то указать его номер.

Входные данные
Входные данные находятся в файле input.in.
Первая срока содержит количество домиков N и количество дорог M.
Затем идут M строк файла по три числа в каждой, которые задают дороги: номера домиков, которые являются концами дороги, и длина дороги.

Выходные данные

Выходные данные находятся в файле output.out, который содержит одну строку. Если точка встречи лежит на дороге, то строка содержит три числа: номера конечных домиков этой дороги и расстояние от первого из этих домиков до этой точки. Если точка совпадает с домом, то строка выходного файла содержит номер этого домика и суммарное расстояние от всех домиков до этого домика. Все числа в строках файлов разделены одним или несколькими пробелами.

Пример
input.in
6 9
1 2 2
2 3 3
3 4 15
4 5 5
5 6 6
6 1 20
1 3 7
3 6 5
4 6 8
output.out
3 37
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2012, 18:05     графы
Посмотрите здесь:

Графы C++
C++ Графы
C++ Графы
C++ [C++] графы
C++ Графы
Графы C++
Графы C++
графы C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 23:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru