3 Как устроен файл с графом
Как устроен файл с графом
Каждая строка файла — одно ребро: три числа через пробел.
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 7 5.5 означает: есть ребро из вершины 1 в вершину 7 длиной 5.5. Рёбра ориентированные (только в одну сторону) и взвешенные (у каждого своя длина). Порядок строк в файле произвольный.
Из вершины 1 в вершину 100 ведут разные пути: напрямую (длина 12), через 4 (2.5 + 8.0 = 10.5) и через 7 (5.5 + 2.0 = 7.5). Кратчайший — через 7, его длина 7.5, а в ответе нужна целая часть — 7.