Antrenament OJI · Grafuri · clasa a 11-a
Drumuri minime cu costuri (Dijkstra)
Cerință
Graful neorientat este conex și are costuri pozitive pe muchii. Afișează costul minim al drumului de la nodul 1 la fiecare nod.
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie n și m, apoi m linii x y c (muchie de cost c).
Date de ieșire
n numere pe o linie (pentru nodul 1 se afișează 0). Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 50 000, 1 ≤ c ≤ 1000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 5 1 4 376 2 3 330 1 3 472 1 2 132 3 4 270
0 132 462 376
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Dijkstra cu coadă de priorități: scoți mereu nodul cu distanța provizorie minimă. Rezultatul corect pentru acest exemplu este: 0 132 462 376.
7 11 1 4 701 2 6 797 1 7 447 4 5 73 4 6 481 1 2 595 3 4 904 1 5 307 1 3 805 2 7 691 3 6 123
0 595 805 380 307 861 447
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Dijkstra cu coadă de priorități: scoți mereu nodul cu distanța provizorie minimă. Rezultatul corect pentru acest exemplu este: 0 595 805 380 307 861 447.
21 28 6 12 581 2 18 707 10 12 797 1 5 936 5 13 37 9 17 491 13 15 716 9 11 286 7 21 198 10 13 25 4 5 269 12 16 259 11 17 40 2 15 39 11 14 112 8 16 444 8 12 527 2 17 350 12 18 710 4 16 821 13 21 645 1 3 599 17 19 3 16 17 603 6 13 67 15 20 993 12 21 276 7 19 94
0 1728 599 1205 936 1040 1816 2148 2239 998 1953 1621 973 2065 1689 1880 1913 2331 1910 2682 1618
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Dijkstra cu coadă de priorități: scoți mereu nodul cu distanța provizorie minimă. Rezultatul corect pentru acest exemplu este: 0 1728 599 1205 936 1040 1816 2148 2239 998 1953 1621 973 2065 1689 1880 1913 2331 1910 2682 1618.
Probleme similare pe PbInfo
Exersează aceeași tehnică și pe PbInfo — acolo găsești și soluții oficiale.
- #1512 Mars — șmenul lui Mars
- #3844 KSum — SSM cu lungime minimă
- #2921 SumeSecv1 — sume parțiale
- #237 Sume — sume parțiale
- #3659 SumMaxSecv — suma costurilor
- #4205 SecvSumS — secvență de sumă S
- #3941 CountSumS — perechi de sumă S
- #4532 SumOfAll — suma subsecvențelor
- #1879 platou2 — secvență crescătoare
- #1639 Secvente3 — ONI 2013
- #2301 secv — ONI gimnaziu 2016
- #2510 vsecvente — lot juniori
- #1090 Secvente2
- #4423 secv2
- #3163 SecvMaxVal
- #334 secventa1 — clasice
- #50 secvmax — secvența de sumă maximă
- #315 secventa
- #190 secvk — secvențe de lungime k
- #217 platou1 — platouri