Fişierul intrare/ieşire:	trilant.in, trilant.out	Sursă	.com 2009, Runda 1
Autor	Serban Andrei Stan	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.55 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Trilant

Într-un graf neorientat G(V,E), un lanţ reprezintă un set de noduri S={x₁,x₂...x_k}, astfel încât există muchie între oricare două noduri consecutive din lanţ. Costul unui lanţ este suma costurilor muchiilor alese pentru a uni x₁ cu x₂, x₂ cu x₃ ... x_k-1 cu x_k. Vom nota un lanţ (x₁,x₂...x_k) prin primul si ultimul său nod (x1,xk).
Definim un trilanţ într-un graf neorientat G(V,E) ca fiind reuniunea a trei lanţuri (A,X),(B,X),(C,X); A,B,C,X ⊆ V, X fiind singurul nod comun celor trei. Costul unui trilanţ este suma costurilor celor trei lanturi care il formează.

Cerinţa

Dându-se un graf neorientat G(V,E), si trei noduri A,B,C ⊆ V determinaţi numărul de trilanţuri de cost minim cu varfurile in A,B,C.

Date de intrare

Pe prima linie a fişierului trilant.in se află două numere naturale N, M separate printr-un spaţiu, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe a doua linie a fişierului de intrare se vor afla numerele naturale A,B,C cu semnificaţia din enunţ.
Următoarele M linii vor conţine câte trei numere P,Q,X descriind faptul ca există muchie de la nodul P la nodul Q cu costul X.

Date de ieşire

Fişierul trilant.out va conţine o singură linie pe care se vor găsi numărul de trilanţuri de cost minim si costul minim găsit.

Restricţii

• 1 ≤ A,B ≤ N ≤ 1 000
• 1 ≤ M ≤ 100 000
• -50 000 ≤ C ≤ 50 000
• Nu vor exista cicluri de cost negativ de lungime ≥ 3
• Oricare trei lanţuri (A,X),(B,X),(C,X) care formează un trilanţ vor fi disjuncte două cate două, mai puţin nodul X (singurul nod comun pe care îl vor avea va fi X)
• Oricare trei lanţuri (A,X),(B,X),(C,X) care formează un trilanţ vor avea lungime ≥ 2 (A ≠ X, B ≠ X, C ≠ X)

Exemplu

Cum se trimit solutii?