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

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

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

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

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.

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

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

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

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

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

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) верным ответом будет 11.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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