Lăptika

Time limit: 0.5s Memory limit: 32MB Input: laptika.in Output: laptika.out

Andi este un băiat buclucaș! Obosit după proba de națională, a luat ciocolata Lăptika, fără a mai declara în scris acest fapt. Acum toată comisia este pe urmele lui! Campusul este compus din NN clădiri, numerotate de la 11 la NN, iar între acestea se află MM drumuri directe, bidirecționale, de un anumit cost. KK dintre acele clădiri reprezintă centre de examinare, din care comisia va pleca în căutarea lui Andi. Se definește distanța dintre două cladiri, AA și BB, ca fiind suma minimă a costurilor drumurilor necesare pentru a ajunge la clădirea BB, plecând din clădirea AA.

Cerință

Cunoscând forma campusului, ajutați-l pe Rara să găsească clădirea cea mai îndepărtată de oricare centru de examinare, pentru a-și putea salva prietenul mai mic.

Date de intrare

Fișierul de intrare laptika.in conține:

  • Pe prima linie, numerele naturale NN, MM şi KK, separate printr-un spațiu;
  • Pe a doua linie, se vor afla indicii celor KK centre de examinare, numere distincte, separate printr-un spaţiu;
  • Pe următoarele MM linii, câte 33 numere de forma { A,B,C }\{\ A, B, C \ \}, care reprezintă un drum direct între nodurile AA și BB, de costul CC.

Date de ieșire

Pe prima linie a fișierului de ieșire laptika.out se va scrie numărul de ordine al celei mai îndepărtate clădiri de oricare centru de examinare și distanța minimă până la aceasta, separate printr-un spațiu.

Restricții și precizări

  • 2N100 0002 \leq N \leq 100 \ 000;
  • N1Mmin(N(N1)/2, 500 000)N-1 \leq M \leq min(N \cdot (N-1)/2, \ 500 \ 000);
  • 1KN1 \leq K \leq N;
  • 1A,BN, AB, 1C1 0001 \leq A, B \leq N, \ A\neq B, \ 1 \leq C \leq 1 \ 000;
  • Campusul este bine gândit, se poate ajunge din fiecare clădire în oricare alta;
  • Dacă există mai multe clădiri convenabile, afișați-o pe cea cu indicele cel mai mic;
  • Poate exista mai mult de un drum direct între 22 clădiri.
# Punctaj Restricții
1 10 K=1,C=1K=1, C=1, pentru orice triplet { A,B,C }\{\ A, B, C \ \}
2 20 C=1C=1, pentru orice triplet { A,B,C }\{\ A, B, C \ \}
3 20 K=1K=1
4 20 N1 000N \leq 1 \ 000
5 30 Fără restricții suplimentare

Exemplu

laptika.in

10 13 4
2 5 6 8
2 1 8
2 4 5
2 7 2
1 4 13
1 6 2
1 7 4
7 5 5
5 8 1
5 10 8
6 3 3
6 9 10
6 8 2
8 9 8

laptika.out

9 8

Explicație

Atât clădirea 9, cât și clădirea 10 sunt cele mai indepărtate și se află la distanța 8 față de cel mai apropiat centru de examinare (8, respectiv 5). Cum 9 este mai mic decat 10, acesta va fi numărul afișat.

Log in or sign up to be able to send submissions!