ЕГЭ-23. Анализ графов

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины самого длинного пути из вершины с номером 1 в вершину с номером 100. Под длиной пути понимается сумма весов рёбер, составляющих путь.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Для каждой вершины, достижимой из вершины с номером 1, найдена длина кратчайшего пути до неё. Запишите в ответе целую часть наибольшей из этих длин.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 647. Существование хотя бы одного такого пути гарантируется.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть наибольшего веса ребра, ведущего в вершину с номером 100.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных вершин, упомянутых в файле. Вершина считается упомянутой, если её номер встретился хотя бы в одной строке — как номер начала ребра или как номер конца.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. Значения L и M не превосходят 1000. Значение W не превосходит 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Ребро одностороннее: по нему можно пройти только из L в M.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Под длиной пути понимается сумма весов рёбер, составляющих путь.

Файл маленький, поэтому задачу можно решить без программы — выписав все пути.

Задача решается с использованием прилагаемых файлов.

В текстовом файле graf.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных (L, M) и одно положительное (W) вещественное число. L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в M. Ребро одностороннее: по нему можно пройти только из L в M.

Найдите и запишите в ответе количество различных путей, ведущих из вершины с номером 1 в вершину с номером 100.

Файл маленький, поэтому задачу можно решить без программы — выписав все пути.