Автор: | А. Баранов | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 2 Мб | |
Выходной файл: | output.txt |
Одна курьерская компания, занимающаяся междугородными перевозками крупногабаритных грузов, решила упростить жизнь своим сотрудникам. Для этого перед программистами поставили задачу, определить наиболее короткие маршруты, по которым можно было бы доставлять грузы между различными населенными пунктами.
В качестве входных данных им выдали дорожную карту, представленную в виде взвешенного графа, вершины которого отвечают за населенные пункты, а ребра обозначают соединяющие их двусторонние магистрали. Каждое ребро имеет вес, указывающий длину соответствующей магистрали.
На выходе требуется получить список кратчайших маршрутов между всеми возможными парами вершин в таком графе. При этом среди них приоритетными считаются маршруты с максимально возможным числом остановок в промежуточных пунктах, т.е. проходящие через как можно большее число вершин.
В начале входного файла "input.txt" записаны два натуральных числа: n — число вершин и m — число соединяющих их ребер. Далее следует набор из m таких ребер, каждое из которых представлено тройкой целых чисел: (ai, bi) — номера вершин, wi — вес ребра. При этом полагается, что нумерация вершин начинается с нуля.
В выходной файл "output.txt" следует построчно вывести маршруты, удовлетворяющие условию задачи и представленные в виде последовательностей из номеров вершин. Если для какой-либо пары вершин существует более одного такого маршрута, достаточно будет вывести любой из них.
Гарантируется, что исходный граф является связным, т.е. между любой парой его вершин можно проложить маршрут.
2 ≤ n ≤ 200, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,
0 ≤ (ai, bi) < n, 0 < wi ≤ 10
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|