Fisa de lucru 3

Probleme propuse:

▪ Intre n statii spatiale se stabilesc trasee. Se cunosc traseele directe intre perechi de statii si distanta dintre ele. Sa se determine drumul minim intre doua statii date stiind ca nu pot fi doua statii pare una dupa cealalta. Sa se afiseze drumul de la statia x la statia y.

▪ Reteaua de strazi a unui oras este reprezentata prin nodurile intersectii ale orasului. Din intersectiile A si B pleaca doi pietoni spre intersectiile x, respectiv y. Ei conosc bine orasul si merg spre destinatie pe drumul minim. Stabiliti daca traseele au trecut prin puncte comune si care sunt aceste intersectii. Determinati daca exista intersectiile in care s-au intalnit.

▪ Intr-o tabara, elevii au n puncte de plecare (cantina, corturile, stejarul cel batran etc.). Initial, deplasarea intre oricare doua puncte se face intr-un timp t, insa organizatorii au amplasat m obstacole pe traseele dintre aceste puncte. Cu fiecare obstacol care trebuie depasit, elevii pierd 30 de secunde. Pe un traseu pot fi mai multe obstacole. Elevii vor sa ajunga din punctul X in punctul Y, pe drumul cel mai scurt. Scrieti un program care citeste n, X, Y. Apoi m perechi de puncte intre care sunt amplasate obstacole si afiseaza drumul cel mai rapid intre X si Y.

Se da un graf orientat cu N noduri si M arce.

Cerinta

Sa se determine lungimea minima a drumului de la nodul 1 la fiecare din nodurile 2, 3, ..., N-1, N si sa se afiseze aceste lungimi. Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.

Date de intrare

Fisierul de intrare dijkstra.in contine pe prima linie numerele N si M, separate printr-un spatiu, cu semnificatia din enunt. Urmatoarele M linii contin, fiecare, cate 3 numere naturale separate printr-un spatiu A B C semnificand existenta unui arc de lungime C de la nodul A la nodul B.

Date de iesire

In fisierul de iesire dijkstra.out veti afisa pe prima linie N-1 numere naturale separate printr-un spatiu. Al i-lea numar va reprezenta lungimea unui drum minim de la nodul 1 la nodul i+1.

Restrictii

• 1 ≤ N ≤ 50 000

• 1 ≤ M ≤ 250 000

  • Lungimile arcelor sunt numere naturale cel mult egale cu 1 000.

  • Pot exista arce de lungime 0

  • Nu exista un arc de la un nod la acelasi nod.

  • Daca nu exista drum de la nodul 1 la un nod i, se considera ca lungimea minima este 0.

  • Arcele date in fisierul de intrare nu se repeta.

Exemplu

Indicatii de rezolvare

Exista o descriere a algoritmului pe wikipedia.

O rezolvare de complexitate O(N²) obtine 40 de puncte si se poate gasi aici.

O rezolvare in O(MlogN) folosind un heap obtine 100 de puncte si se poate gasi aici. O descriere a acestei structuri de date puteti gasi tot pe wikipedia. O implementare de aceeasi complexitate foloseste in loc de heap structura de date numita SET, care este de fapt un arbore binar echilibrat si permite interogarea costului minim si modificarea costurilor in timp logaritmic. Aceasta abordare se gaseste aici si are avantajul ca necesita un cod mult mai scurt. Totusi, ea este mai inceata decat solutia cu heap-uri si, in consecinta, obtine doar 80 de puncte.

O alta rezolvare utila in concursuri este algoritmul Bellman-Ford cu coada. Desi are complexitatea teoretica O(N*M), in practica solutia se dovedeste destul de rapida pentru a trece toate testele.