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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
blanc_miami
0 / 0 / 0
Регистрация: 17.11.2011
Сообщений: 16
#1

графы - C++

12.05.2012, 18:05. Просмотров 405. Ответов 0
Метки нет (Все метки)

Условие
Вводится число 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++
Помогите плиз! Есть задача: Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует...

Графы - C++
Написать на C++ класс, описывающий граф/орграф. Класс должен поддерживать следующую функциональность: • определение числа вершин; ...

Графы (с++) - C++
Помогите с задачей: граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа. Добавлено через 1 час 34...

Графы - C++
помогите пожалуйста написать программу удаления вершины: а)с сохранением связей б)без сохранения связей желательно на с билдер

*Графы* - C++
пожалуйсто помоги мне с программой.умоляю!!! вот тема: реализация различных типов графов и операций над ними. зараннее спасибо.

Графы - C++
Задача: По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных...

Графы - C++
Задана система односторонних дорог(вбивается рандомно или вручную). Найти два города и соединяющий их путь, который проходит через каждую...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru