You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers NMS, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of N integers — distances from vertex S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤ N, M ≤ 1000.
All weights are less than 1000 by absolute value.
You are to write a program that finds shortest distances between all pairs
of vertices in a directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers N and M, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a matrix of size NxN.
Element in the j-th column of i-th row mush be the shortest distance between
vertices i and j.
The distance from the vertex to itself is considered to be 0.
If some vertex is not reachable from some other,
there must be empty space in corresponding cell of matrix.
Constraints
0 ≤ N ≤ 100.
All weights are less than 1000 by absolute value.
Вам задан связный ориентированный граф с N вершинами и M ребрами.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Формат входного файла
Граф задан во входном файле следующим образом: первая строка содержит числа N и M.
Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до
N - номера начала и конца ребра.
Формат выходного файла
На первой строке выведите число K - количество компонент сильной связности в заданном графе.
На следующей строке выведите N чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
В ДВФУ произошло укрупнение кафедры информатики.
В связи с этим встал вопрос выборе нового заведующего кафедрой.
На кафедре работает много преподавателей и непросто выбрать самого достойного.
Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i
определили следующие числа:
mi — уровень познаний в математике;
pi — уровень познаний в программировании;
ti — преподавательское мастерство;
Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области.
Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой
в том и только том случае, когда для него не найдётся такого j-того преподавателя,
что одновременно mj > mi, pj > pi, tj > ti.
Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.
Формат входного файла
Входной файл содержит натуральное число n — количество преподавателей.
Далее следует n троек натуральных чисел mipiti.
Формат выходного файла
Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.
