Лабораторная 7. Ориентированные графы

Граф состоит из вершин и дуг, каждая из которых имеет номер и натуральный весовой коэффицент, может быть заблокирована для прохождения. Каждая дуга дополнительно содержит информацию об исходной и целевой вершине. Любые две вершины могут соединяться любым количеством дуг. Для простоты будем считать, что вершины и дуги нумеруются от единицы, в нумерации не может быть разрывов (например, может быть задана последовательность вершин 4,2,1,3, но не может - 55,3,1,2).

Граф задается двумя строками входных данных:

Первая строка содержит информацию о вершинах в виде тройки значений на каждую: номер вершины, вес вершины, признак блокировки. Номера вершин не повторяются. Элементы в строке отделяются друг от друга пробелом.

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

Третья и последующая строки содержат набор последовательных нумерованных операций над графом:

  1. Вывести в первую строку список весовых коэффициентов вершин, в последующие строки - матрицу смежности графа. На пересечении строк и столбцов матрицы смежности указывать весовые коэфициенты дуг в скобках. Если несколько дуг однонаправлено соединяют две вершины, их весовые коэффициенты выводить через пробел и объединять скобками. Если дуга или вершина заблокирована, то ее весовой коэффициент выводится отрицательным значением. По возможности обеспечить выравнивание столбцов.
  2. Вывести информацию о вершине по ее номеру. После номера может следовать вес и факт блокировки вершины, что означает изменение ее параметров перед выводом. Если один из параметров менять не нужно, ввести в его позицию значение -1
  3. Вывести информацию о дуге по ее номеру. После номера может следовать вес и факт блокировки дуги, что означает изменение ее параметров перед выводом. Если один из параметров менять не нужно, ввести в его позицию значение -1
  4. Найти путь в графе между двумя вершинами. Результат вывести в две строки - номера вершин и номера дуг.
  5. Найти простой путь в графе между двумя вершинами. Результат вывести в две строки - номера вершин и номера дуг.
  6. Найти кратчайший путь в графе по количеству вершин между двумя вершинами. Результат вывести в две строки - номера вершин и номера дуг.
  7. Найти кратчайший путь в графе по весу пути между двумя вершинами. Результат вывести в две строки - номера вершин и номера дуг.
Задание може здавать блоками, последовательно. Реализация функциональных возможностей 1-6 дает по 10 баллов, 7 - 20 баллов (более - при своевременной сдаче работы).