180 Drumuri minime

[•domino]

Aici puteţi discuta despre problema Drumuri minime.

[u-92]

imi poate recomanda cineva ce functie sa folosesc pt a calcula logaritmul?
in concurs am testat diferite variante si era foarte dubios.. folosind "log" cu tipul double iau 0.. insa daca schimb in "log10" si tipul in long double iau 80, cu "logl" si tipul long double iau 5
 

[•domino]

Mie mi-a mers ok cu log() si double.

[u-92]

am descoperit greseala      
eu comparam pur si simplu.. acum am bagat un eps = 1e-10 si merge de 100

[•silviug]

Asa se invata cel mai bine: gresind in concursuri!

Silviu

[•pauldb]

Iau 85 de puncte    (pic testele 16,19,20 cu WA)... Ce e asa de special la testele astea? Are cineva vreo idee unde gresesc?

[•gogu]

Incearca sa folosesti o precizie mai mare cand compari egalitatea dintre 2 numere reale. Ar trebui sa mearga cu 1e-8 de exemplu.

[•pauldb]

Da, asta era, multumesc.  

[•the_godfather]

Imi spune si mie cineva daca e corect cum calculez nr de drumuri de cost minim?
Eu calculez cu djickstra drumul minim de la 1 la un nod iar daca il gasesc initializez nr de drumuri minime pt. drumul respectiv cu nr. de drumuri de cost minim de la nodul anterior de la care am cautat costul minim.
Daca e egal adun numarul de drumuri prin nodul prin care e egal.
Si iau 5 puncte fara logaritm iar cu 0.
Ma ajuta si pe mine cineva.
Va rog.Multumesc!
Sau daca nu sa imi dea cineva un test mai mare si raspunsul corect sa verific.(nu unul oficial, ca oricum nu se dau )
Am reusit sa iau 15 puncte dar nu stiu cum sa fac aproximarea aia cu 10e-10 sau -8.Ce intoarce aia si cum o folosesc?

[u-92]

cand lucrezi cu numerele reale apar erori de precizie (de exemplu sqrt(2) nu va intoarce toate zecimalele lui radical din 2).. de aceea (in cazul problemei dmin) iti iei o marja de eroare

Cod:

eps = 0.0000000001 (echivalent cu 1e-10)

acum, daca ai doua numere reale a si b, cand vrei sa testezi daca sunt egale
vei folosi

Cod:

if( abs(a-b) <= eps )

( modulul diferentei lor sa fie mai mic sau egal decat marja de eroare )

ps: sunt probleme in care se cere rezultatul cu o marja de eroare de 0.001 (de exemplu), acolo vei putea alege epsilon = 0.001. (deci 1.445690994 il vei considera egal cu 1.4458906956)

[•Marius]

Si eu am folosit algoritmul lui The_Godfather mai putin problema aproximarilor si am luat 10 puncte...  

Cred ca gresesc la update-ul numarului de drumuri minime... Ce va da pentru

Cod:

5 7
1 2 1
2 3 1
3 4 1
2 4 1
1 4 1
1 5 1
4 5 1

Poate asa imi dau seama unde gresesc (inclusiv pe hartie)   !

[•sarabogdan]

1 3 2 3

[u-92]

costul energetic al unei legaturi este un numar intreg din intervalul [2, 10^9]

[•filipb]

Imi spune si mie cineva daca e corect cum calculez nr de drumuri de cost minim?
Eu calculez cu djickstra drumul minim de la 1 la un nod iar daca il gasesc initializez nr de drumuri minime pt. drumul respectiv cu nr. de drumuri de cost minim de la nodul anterior de la care am cautat costul minim.
Daca e egal adun numarul de drumuri prin nodul prin care e egal.
Si iau 5 puncte fara logaritm iar cu 0.
Ma ajuta si pe mine cineva.
Va rog.Multumesc!

In momentul cand afli in djikstra nodul alb (dupa explicatia din Cormen) care are distanta pana la 1 minima, atunci faci numararea: aduni toate numerele de forma P

• , unde x e un nod a. i. sa existe muchia x - NOD_CURENT_OPTIM, si d
• + COST_MUCHIE_CURENTA = d[NOD_CURENT_OPTIM]... asa mi se pare cel mai logic si merge usor fara sa iti bati capul pe greseli ( nu faci numararea in timpul relaxarii muchiilor care pornesc din NOD_CURENT_OPTIM, o faci inainte... )

[•the_godfather]

Multumesc tuturor pentru ajutor!Acu merge si le egaleaza.
Acu iau 10 puncte am sa vad de ce.
Cat da pentru testul asta?

Cod:

50 69 
22 33 1347 
11 43 1710 
5 21 354 
1 11 559 
27 45 1157 
9 29 66 
38 15 1480 
1 23 774 
49 5 1836 
37 36 1179 
39 30 397 
12 49 548 
28 20 815 
10 21 83 
7 48 719 
17 11 1019 
47 27 1803 
32 16 170 
42 6 901 
45 5 205 
47 29 691 
2 25 1317 
39 7 159 
20 9 558 
8 42 1194 
40 13 854 
46 16 1022 
18 48 793 
48 6 1428 
18 28 33 
18 11 1190 
27 36 98 
2 8 1241 
47 5 158 
34 41 193 
21 13 588 
29 12 1195 
44 34 1642 
14 34 1813 
28 17 1659 
21 46 681 
34 39 1554 
7 49 1336 
21 40 396 
34 48 1621 
22 39 1683 
5 6 866 
24 43 3 
37 34 1698 
25 35 955 
43 12 99 
28 45 1493 
2 1 193 
7 48 611 
48 45 567 
3 49 759 
14 42 958 
17 20 224 
42 40 871 
4 9 565 
35 17 86 
43 40 984 
40 10 1553 
48 23 503 
48 38 1276 
9 35 498 
13 36 1897 
31 44 1072 
47 1 1051

Mie imi da:
1 3 1 1 2 1 1 1 1 1 2 1 2 1 1 1 1 0 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 3 1 2 1 1 1 1 1 1 3 0

[•the_godfather]

In momentul cand afli in djikstra nodul alb (dupa explicatia din Cormen) care are distanta pana la 1 minima, atunci faci numararea: aduni toate numerele de forma P

• , unde x e un nod a. i. sa existe muchia x - NOD_CURENT_OPTIM, si d
• + COST_MUCHIE_CURENTA = d[NOD_CURENT_OPTIM]... asa mi se pare cel mai logic si merge usor fara sa iti bati capul pe greseli ( nu faci numararea in timpul relaxarii muchiilor care pornesc din NOD_CURENT_OPTIM, o faci inainte... )[/quote]
  
  Cum o fac inainte. Ca trebuie sa calculez mai intai costul minim pentru nodul respectiv si apoi adun toate drumurile de la nodul anterior x daca is egale si daca nu initializez cu drumurile pt nodul respectiv.
  ceva de forma:

Cod:

for(j=2;j<=n;j++)
  if(s[j]==0)
  if(abs(d[j]-(d[poz]+a[poz][j]))>eps&&a[poz][j]!=0&&j!=poz)
  {
   p[j]=p[poz];
   d[j]=d[poz]+a[poz][j];
  }else
  if(abs(d[j]-(d[poz]+a[poz][j]))<=eps&&a[poz][j]!=0&&j!=poz)
    p[j]+=p[poz];

unde poz este nodul 1-poz-poz-j.

[•filipb]

Mie imi da

Cod:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

Si cred ca e si bine, din moment ce am luat 100

Mai, dupa ce afli nodul ala, te gandesti care pot fi predecesorii lui in arborele de drumuri minime ( asta inseamna conditiile alea doua ) si aduni valorile corespunzatoare pt. predecesori.

[•Marius]

Eu unul am determinat distanta minima de la nodul 1 la fiecare dintre celelalte noduri...
Pentru a numara cate drumuri de lungime minima sunt pana la un nod p am facut asa:

Cod:

pentru "fiecare nod q adiacent lui p" executa
     daca "nu se stie cate drumuri sunt pana la q" atunci
          "calculeaza pentru nodul q"
     "actualizez datele nodului p"

Mi-am exprimat din nou parerea, deoarece am incercat si ca filipb si ca The_Godfather si ca mine si iau aceleasi 70 de puncte. Precizia e 1e-10... In plus a inceput sa imi placa Dijkstra   .

[Tabara Mihai]

Imi explica si mie de ce cu if() - ul asta merge de 100

Cod:

if ( d[j->vf] - (d[k] + dis ) > eps  )
{
           d[j->vf] = d[k] + dis;
           nr[j->vf] = nr[k]%104659;
}

si cu if-ul asta ia 0 puncte

Cod:

if ( d[j->vf]  > d[k] + dis  )
{
           d[j->vf] = d[k] + dis;
           nr[j->vf] = nr[k]%104659;
}

De ce e asa mare diferenta intre "if ( d[j->vf] - (d[k] + dis ) > eps  )" si "if ( d[j->vf]  > d[k] + dis  )".
Precizez ca am folosit eps = 1e-10.

 

[•pauldb]

Pai e evident. La primul if nu folosesti eps ca sa eviti erorile de precizie.

[•Darth_Niculus]

Am definit astea:

Cod:

#define NMAX 1501
#define MMAX 2501
#define INFY 0x3f3f3f3f
#define ALAS 104659
#define eps 1e-10

Apoi in interiorul lui Dijkstra, dupa ce am descoperit nodul in care s-a ajuns cu cost minim.... adica , cand ma duc pe vecinii nodului in care s-a ajuns cu costu' minim.

Cod:

     for (i=1;i<=n;i++)
        if (A[NOD_MAX][i])
          {
           if ((C[NOD_MAX] * A[NOD_MAX][i] / C[i]) < eps)
             {
              C[i] =C[NOD_MAX] * A[NOD_MAX][i];
              D[i] = D[NOD_MAX] % ALAS;
             }
             else
           if (C[NOD_MAX] * A[NOD_MAX][i] == C[i] )
             {
              D[i]+=D[NOD_MAX];
              D[i]=D[i] % ALAS;
             }
          }

Asa iau 10 puncte, daca scot eps-ul si fac fara iau 5 puncte.
Nu vad ce alte erori de precizie pot aparea dupa ce includ si eps-ul in program.

[•astronomy]

mi-a sarit in ochi al doilea if cand verifici egalitatea.. nu mai iei in considerare eps

p.s: scapa si de modulo, consuma foarte mult timp de executie

[•peanutz]

Pe testul pus de Marius mie imi da un raspuns diferit de cel al lui sarabogdan si anume 1 1 3 4. Cine are dreptate?(cu sursa de 100)

[•cos_min]

Si mie imi da 1 1 3 4...tot cu sursa de 100 pcte.

[•Dastas]

Mie imi da 5 4 3 4 cu sursa de 100... care-i raspunsul pana la urma?

1 1 3 4 eu zic ca sigur nu-i corect. De la nodul 1 pana la 2 sunt clar mai multe drumuri ( 1 - 2, 1 - 4 - 2, 1 - 5 - 4 - 2, 1 - 5 - 4 - 3 - 2, 1 - 4 - 3 - 2, daca am facut bine )

Nici mie nu imi da bine pentru celelalte noduri.. oricum nu cred ca are importanta, ca se precizeaza ca nu poate exista un cost mai mic ca 2.