Задача Кратчайшие пути

@dimpa · Регистрация: 22.10.2019

Студворк — интернет-сервис помощи студентам

Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта

Взвешенный граф с N вершинами задан своими M ребрами Ei, возможно
отрицательного веса. Требуется найти все кратчайшие пути от вершины S до
остальных вершин. Если граф содержит отрицательные циклы, вывести
IMPOSSIBLE. Если от вершины S до какой-либо из вершин нет маршрута, то
в качестве длины маршрута вывести слово UNREACHABLE/
Вершины графа нумеруются, начиная с нуля.

3 ≤ N ≤ 800
1 ≤ M ≤ 30000
-1000 ≤ Wi ≤ 1000

Формат входных данных:

N M S
S1 E1 W1
S2 E2 W2
...
Формат выходных данных:

IMPOSSIBLE
или
D1 D2 D3 … DN
Где Di может быть UNREACHABLE

@StalinStr · 04.11.2019, 21:24

Братан, ладно я спрашиваю что и как сделать, но редко задания загружаю ибо стараюсь все сам сделать насколько могу, но ты походу решил всю контрольную сегодня за 10 лет в один день решить.а.хаххахахха

@dimpa · 04.11.2019, 21:28 **[ТС]**

сдавать просто скоро, хых, поэтому такая фигня, сам просто уже не допираю как делать

@StalinStr · 04.11.2019, 21:36

Сообщение от dimpa

сдавать просто скоро, хых, поэтому такая фигня, сам просто уже не допираю как делать

Аххх..понимаю, такая же фигня.. Но я стараюсь)

@vvm28 · 05.11.2019, 12:50

dimpa, пишите что вы уже сделали.
То есть выставляете часть вашего кода java, и задаете вопросы уже по нему.

Вы можете использовать любой из существующих ныне алгоритмов:

Флойда-Уоршелла
Дейкстры
Дейкстры для разреженных графов
Форда-Беллмана
Волновой алгоритм
Алгоритм Йена

Можете даже попробовать придумать свой алгоритм. Задайте конкретный вопрос и вам на него быстро дадут ответ.

Новые блоги и статьи Все статьи Все блоги /
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .

@dimpa -13 / 0 / 0 Регистрация: 22.10.2019 Сообщений: 35

	Задача Кратчайшие пути 04.11.2019, 21:17. Показов 3476. Ответов 4 Метки нет (Все метки) Ограничение по времени: 2 секунды Ограничение по памяти: 64 мегабайта Взвешенный граф с N вершинами задан своими M ребрами Ei, возможно отрицательного веса. Требуется найти все кратчайшие пути от вершины S до остальных вершин. Если граф содержит отрицательные циклы, вывести IMPOSSIBLE. Если от вершины S до какой-либо из вершин нет маршрута, то в качестве длины маршрута вывести слово UNREACHABLE/ Вершины графа нумеруются, начиная с нуля. 3 ≤ N ≤ 800 1 ≤ M ≤ 30000 -1000 ≤ Wi ≤ 1000 Формат входных данных: N M S S1 E1 W1 S2 E2 W2 ... Формат выходных данных: IMPOSSIBLE или D1 D2 D3 … DN Где Di может быть UNREACHABLE 0

@StalinStr 6 / 9 / 0 Регистрация: 19.10.2019 Сообщений: 194
	04.11.2019, 21:24
	Братан, ладно я спрашиваю что и как сделать, но редко задания загружаю ибо стараюсь все сам сделать насколько могу, но ты походу решил всю контрольную сегодня за 10 лет в один день решить.а.хаххахахха 0

@dimpa -13 / 0 / 0 Регистрация: 22.10.2019 Сообщений: 35
	04.11.2019, 21:28 [ТС]
	сдавать просто скоро, хых, поэтому такая фигня, сам просто уже не допираю как делать 0

@vvm28 771 / 539 / 67 Регистрация: 22.12.2013 Сообщений: 2,498 Записей в блоге: 26
	05.11.2019, 12:50
	Сообщение было отмечено dimpa как решение Решение dimpa, пишите что вы уже сделали. То есть выставляете часть вашего кода java, и задаете вопросы уже по нему. Вы можете использовать любой из существующих ныне алгоритмов: Флойда-Уоршелла Дейкстры Дейкстры для разреженных графов Форда-Беллмана Волновой алгоритм Алгоритм Йена Можете даже попробовать придумать свой алгоритм. Задайте конкретный вопрос и вам на него быстро дадут ответ. 0

Задача Кратчайшие пути

Решение