Банк заданий
ЕГЭ по информатике Задание №23 Анализ графов, Построение оптимального пути между вершинами

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

Найдите и запишите в ответе минимально возможное количество рёбер на пути из вершины с номером 7 в вершину с номером 93. Существование хотя бы одного такого пути гарантируется. Для выполнения этого задания следует написать программу.

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 7 в вершину с номером 12 верным ответом будет 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1mKnaqT1pvb1lyD1fcohHt2jvB6I8LD5y/view

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

Найдите и запишите в ответе максимально возможное количество рёбер на пути из вершины с номером 17 в вершину с номером 83. Существование хотя бы одного такого пути гарантируется. Для выполнения этого задания следует написать программу.

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 1 в вершину с номером 12 верным ответом будет 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1ihN6eBpRg8-LUoXEuQo1aXN9jXsYE5xZ/view

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

Найдите и запишите в ответе минимально возможное количество рёбер на пути из вершины с номером 19 в вершину с номером 74. Существование хотя бы одного такого пути гарантируется. Для выполнения этого задания следует написать программу.

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12 верным ответом будет 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1f3wqM8Py4dNp-rYJ3mYXkHA_bwagcV1W/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1hdWNmqSsCjRD333Oio1nav-kPmxTcrS_/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/16W_t9KNDGd0bQktkogx9fX4XXGjQOlMJ/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, не проходящего через вершину с номером 4, верным ответом будет 9.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1dYOMBZJ1udTUpT-s2VjDvLizd1n3nzVB/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера верным ответом будет 7.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1jWA_uzlccY_s2Bgx4L5zN8mKsnqeEnjE/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера верным ответом будет 10.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1cyBj-NfZttsTl-FHaNdvEZz1ACVFwmPZ/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера верным ответом будет 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1YuyI5m-qNkCKs7XlWd9RzpvCRAvOQJoo/view

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

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

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

Типовой пример организации данных во входном файле для графа на рисунке

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера верным ответом будет 40.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1EH1iAdRgr0t3OKvJAxJa4EMW6rMQ3E1O/view