Кратчайшие пути в графе


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38521. Кандидаты в не кратчайший путь
Темы: Алгоритмы на графах    Кратчайшие пути в графе   

Дан неориентированный связный взвешенный граф с 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
 Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин.

 
ID 38585. Транзитный путь
Темы: Алгоритмы на графах    Кратчайшие пути в графе    Обход в ширину   

Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины ai и bi и имеет длину ci.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины xj к вершине yj через вершину K.

Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины ai и bi (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними ci (\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа xj, yj (\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ). 
Заданный граф является деревом.

Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.

 

Примеры
№ Входные данные Выходные данные Пояснение
1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5		 3
2
4		 Кратчайшие пути для трех запросов следующие:

Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3
Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2
Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4
2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7		 5
14
22		 Путь для каждого запроса должен проходить через вершину K = 2.
3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10		 17000000000  

 
ID 38655. Метро Давилона
Темы: Алгоритмы на графах    Кратчайшие пути в графе   

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=105) и M (0<=M<=2*105). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=106, pi ≠ qi. 

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

 

Примеры
№ Входные данные Выходные данные Пояснение
1 3 3
1 2 1
2 3 1
3 1 2		 1 Используйте линии компании 1:
1 → 2 → 3.
Стоимость проезда 1 сантик.
2 8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5		 2 Сначала используйте линии компании 1:
1 → 3 → 2 → 5 → 6.
Затем используйте линии компании 5:
6 → 7 → 8.
Стоимость проезда 2 сантика.
3 2 0 -1