1935: Розмальовка
Перегляд у форматі PDFДано граф на ~n~ вершинах і ~m~ неорієнтованих, зважених ребрах. Кожне ребро розфарбовано в червоний або зелений кольори. Потрібно знайти цикл що містить вершини ~a~ і ~b~ дані в вхідних даних ~(a \ne b)~, і при цьому містить ребра обох кольорів. Виведіть найменшу можливу вагу такого циклу.
Цикл в неорієнтованому графі — це шлях у графі такий, що кожне ребро в ньому зустрічається не більше одного разу, а початок і кінець шляху — одна і та ж вершина.
Вага циклу — це сума ваг його ребер.
Input
У першому рядку записано два цілі числа ~n~ і ~m~ — кількість вершин і ребер у графі: ~(1 \le n \le 10^5)~, ~(1 \le m \le 2*10^5)~
У другому рядку записано два цілі числа ~a~ і ~b~ — вершини, які має містити цикл: ~a \ne b~, ~(1 \le a,b \le n)~
У наступних ~m~ рядках міститься по чотири цілі числа ~u_i~ ~v_i~ ~w_i~ ~c_i~, які описують ребро, що з'єднує ~u_i~ i ~v_i~, з вагою ~w_i~, та кольором ~c_i~ (0 — червоний, 1 — зелений): ~(1 \le u_i,v_i \le n)~, ~(1 \le w_i \le 10^9)~, ~(0 \le c_i \le 1)~
Output
Виведіть одне ціле число — найменшу можливу вагу циклу, що містить вершини ~a~ і ~b~ і при цьому містить ребра обох кольорів.
Sample Input 1
7 8
1 4
1 2 1 0
2 3 1 0
3 4 1 0
4 5 1 0
5 6 1 0
6 1 1 0
1 7 1 1
7 6 1 0
Sample Output 1
7
Notes
Зверніть увагу, що без умови про те, що цикл має містити ребра обох кольорів, відповідь була б ~6~
Коментарі
Чи може граф містити кратні ребра? Іншими словами чи може між вершинами "1" та "2" бути більше ніж одне ребро?
так
Поясніть чому в семплі найменший шлях буде 7. І чому не враховуючи умову відповідь буде 6
Цикл вагою 6 містить лише червоні ребра - це містить примітка до прикладу вхідних. За вимогами умови треба знайти цикл, що містить ребра обох кольорів.