Aplicația 2

Scrieți un program care citește un graf dat prin lista muchiilor și care să determine arborele parțial de cost minim. Prin costul unui arbore se înțelege suma costurilor muchiilor din arbore.
Fișier de intrare: apm.in
Linia 1: n m - numărul de noduri respectiv de muchii din graf
Linia 2: X1 Y1 C1- există muchie între nodurile X1 și Y1 de cost C1 [...]
Linia m+1: Xm Ym Cm- există muchie între nodurile Xm și Ym de cost Cm
Fișier de ieșire: apm.out
Linia 1: S1 D1[...]
Linia n-1: S(n-1) D(n-1), unde Si Di reprezintă descrierea muchiei i din arbore. (Ordinea în care acestea apar nu contează).

Folosiți algoritmul lui Kruskal organizând costurile muchiilor într-un heap.
Indicație

Aplicația 3

Se dă un graf prin lista muchiilor și două vârfuri din graf. Să se determine drumul de cost minim dintre cele două vârfuri date. Prin costul unui drum se înțelege suma costurilor muchiilor ce aparțin drumului.
Fișier de intrare: drum.in
Linia 1: n m - numărul de noduri respectiv de muchii din graf
Linia 2: X1 Y1 C1- există muchie între nodurile X1 și Y1 de cost C1 [...]
Linia m+1: Xm Ym Cm- există muchie între nodurile Xm și Ym de cost Cm
Linia m+2: S D - cele două vârfuri pentru care trebuie calculat drumul minim.
Fișier de ieșire: drum.out
Linia 1: C- costul drumului minim.

Folosiți algoritmul lui Dijkstra optimizând căutarea valorii minime la un anumit pas. Pentru a putea extrage minimul în timp [log n] organizați vectorul de valori temporare ca un heap.
Indicație

Probleme Propuse:

Ușoare:

1.Dijkstra
2.Kruskal
3.C. Heap Operations
4.506. Relative Ranks

Medii:

1.Ramen
2.Cezar1
3.Numar6

Dificile:

1.Volum
2.Catmin
3.Pitici1
4.862. Shortest Subarray with Sum at Least K
5.F. Heaps