Задача
Дан неориентированный связный взвешенный граф с
N вершинами и
M ребрами, который не содержит ни петель, ни двойных ребер.
I-е (
\(1<=i<=M\)) ребро соединяет вершину
ai и вершину
bi на расстоянии
ci. Будем считать, что петля - это ребро, где
\(a_i=b_i\) (
\(1<=i<=M\)), а двойные ребра - это два ребра, где
\((a_i,b_i)=(a_j,b_j) \) или
\((a_i,b_i)=(b_j,a_j)\) (
\(1<=i<j<=M\)). Связный граф - это граф, в котором есть путь между каждой парой разных вершин. Найдите количество ребер, которые не входят ни в один кратчайший путь между любой парой различных вершин.
Входные данные
В первой строке задаются два целых числа
N и
M (
\(2<=N<=100\),
\(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). Далее идет
M строк по три целых числа в каждой строке:
ai,
bi,
ci (
\(1<=a_i, b_i<=N\),
\(1<=c_i<=1000\)). Данный граф не содержит петель и двойных ребер. Данный граф является связанным.
Выходные данные
Выведите количество ребер в графе, которые не входят ни в один кратчайший путь между любой парой различных вершин.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3 3
1 2 1
1 3 1
2 3 3
|
1
|
В данном графе кратчайшие пути между всеми парами различных вершин следующие:
Кратчайший путь от вершины 1 к вершине 2: вершина 1 → вершина 2, длина пути равна 1.
Кратчайший путь от вершины 1 к вершине 3: вершина 1 → вершина 3, длина пути равна 1.
Кратчайший путь из вершины 2 в вершину 1: вершина 2 → вершина 1, длина пути равна 1.
Кратчайший путь от вершины 2 к вершине 3: вершина 2 → вершина 1 → вершина 3, длина пути равна 2.
Кратчайший путь от вершины 3 до вершины 1: вершина 3 → вершина 1, длина пути равна 1.
Кратчайший путь от вершины 3 к вершине 2: вершина 3 → вершина 1 → вершина 2, длина пути равна 2.
Таким образом, единственное ребро, которое не содержится ни в одном кратчайшем пути, - это ребро длины 3, соединяющее вершину 2 и вершину 3, поэтому на выходе должно быть 1. |
| 2 |
3 2
1 2 1
2 3 1
|
0
|
Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин. |
