Условие задачи | | Прогресс |
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Дан неориентированный связный взвешенный граф с 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
|
Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин. |
| |
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Обход в ширину
Вам дано дерево с 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 |
|
| |
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из 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 |
|
| |
|