OJI 2003 - Zmeu

[cristi8]

isi aminteste cineva problema ?

Mai ştie o mulţime de k perechi de poveşti, semnificând faptul că a doua poveste din pereche nu poate fi spusă după prima poveste din pereche.

....

Iar pe ultimele k linii se află câte o pereche de numere pi şi pj (separate prin câte un spaţiu) ce semnifică faptul că povestea pj nu poate fi spusă după povestea pi.

... nu poate spune a doua poveste din pereche imediat dupa prima, sau daca a spus-o pe prima, pana la sfarsit nu o spune pe a 2a ?

..daca nu mai are voie pana la sfarsit sa o spuna pe a 2a, problema se transforma intr-o gluma proasta... dar nu specifica ca nu au voie sa fie doar
consecutive... si vream sa fiu sigur..

ce parere aveti ?

[•wickedman]

here we go again ...

[cristi8]

:lol:  sa inteleg ca a fost ambigu enuntul problemei si atunci in 2003 si toata lumea vorbea despre asta, si acum m-am trezit si eu sa citesc problema si sa-mi dau seama ?

[•wickedman]

da
a curs multa "cerneala" pe tema asta.

[•newsabbath]

Buna

Se vorbeste despre problema zmeu:
Zmeul le-a inchis pe cele 5 fete ale imparatului in castelul sau. Fat-Frumos a venit sa le scoata din castel, folosind harta pe care i-a dat-o zana buna. Pe harta sunt desenate cele n camere ale castelului, numerotate de la 1 la n si cele m tuneluri dintre camere. De asemenea sunt marcate camerele in care se gasesc fetele si Fat-Frumos, timpul necesar traversarii fiecarui tunel si cele p camere din care se poate iesi din castel.

Cerinta

Determinati timpul minim necesar lui Fat-Frumos pentru a lua cele 5 fete si a le scoate din castel.

Date de intrare

Pe prima linie a fisierului de intrare zmeu.in sunt scrise numerele n, m si p, reprezentand numarul de camere, numarul de tunele si respectiv numarul de iesiri din castel.
Pe a doua linie sunt scrise numerele a 6 camere distincte: primul numar e camera in care se afla Fat-Frumos, iar celelalte 5 sunt camerele fetelor.
Pe urmatoarele m linii sunt cate 3 numere, reprezentand cele m tunele: primele doua reprezinta camerele intre care face legatura tunelul, al treilea timpul necesar traversarii tunelului.
Ultimele p linii contin cate un numar reprezentand camerele din care se poate iesi din castel. Toate numerele sunt intregi strict pozitive, iar numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Prima linie a fisierului zmeu.out va contine un singur numar, timpul minim necesar pentru a porni din camera lui Fat-Frumos, a trece prin camerele celor 5 fete si a ajunge intr-o camera care are iesire in afara. Se va lua in considerare numai timpul traversarii tunelurilor, neglijandu-se timpul traversarii camerelor sau a iesirii din castel.

Am incercat sa rezol problema. Rezultate: fetele mi le afiseaza corect, dar nu imi iese suma ... am lucrat cu Dijkstra fara heapuri.
Daca cineva ma poate ajuta cu o idee...

[•Mishu91]

Folosind Dijkstra/ Bellman-Ford/ Roy-Floyd poți afla distanța între fiecare dintre camere și toate celelalte noduri.
Apoi, faci un backtraking pentru cele 5 noduri, asta însemnând ordinea în care vor fi parcurse, iar distanța finală este distanța de la camera lui FF la primul nod din back + distanța de la primul nod din back la al doilea+ ... + distanța de la 5-lea nod din back la cea mai apropiată cameră de ieșire. Iar rezultatul final este minimul acestor distanțe. N-am încercat, dar cred că merge

[•newsabbath]

Buna
nu stiu daca am voie sa postez sursa aici ... inca nu m-am prins unde am gresit ...

[Later edit] asta este sursa pe care am scris-o pt zmeu ...
daca poate sa imi dea careva o idee ...

Cod:

#include <iostream>

using namespace std;


int n,m,p,ff, f[5], mat[1000][1000], ies[500], viz[1000], d[1000], pre[1000], ;//nr de camere, tunele, iesiri

void citire()
{
    freopen("zmeu.in", "r", stdin);

    scanf("%d%d%d/n", &n, &m, &p);
    scanf("\n");
    scanf("%d", &ff);

    for(int i=1;i<=5;i++)
        scanf("%d", &f[i]);
    scanf("\n");
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        mat[a][b] = c;
        mat[b][a] = c;
    }
    for(int i=1;i<=p;i++)
        scanf("%d\n",&ies[i] );
    for(int i =1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i != j && mat[i][j] == 0)
                mat[i][j] = 333;

}
int dijkstra()
{
   for(int i=1;i<=n;i++)
   {
       d[i] = mat[ff][i];
       pre[i] = ff;
   }
   viz[ff] = 1;
   pre[ff] = 0;
   int pozmin;
   for(int j=1;j<=n;j++)
   {
       int dmin = 333;
       for(int i=1;i<=n;i++)
        if(viz[i] == 0 && dmin > d[i])
        {
            dmin = d[i];
            pozmin = i;
        }
       viz[pozmin] = 1;
       for(int i=1;i<=n;i++)
        if(viz[i] == 0 && d[i]> dmin + mat[pozmin][i])
        {
            d[i] = dmin + mat[pozmin][i];
            pre[i] = pozmin;
        }
   }
   int s = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(i == j)
                s = s + d[i];
    }
}

void afisare()
{
    freopen("zmeu.out", "w", stdout);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ", mat[i][j]);
        printf("\n");
    }
    printf("\n");
      printf("%d",dijkstra());
}



int main()
{
    citire();
    afisare();
    dijkstra();

    return 0;
}

Editat de moderator: Foloseste tagul [ code ] cand postezi cod si editeaza-ti mesajele mai vechi in loc sa postezi de 2 ori consecutiv.

[•Mishu91]

Din ce văd, la tine funcția dijkstra nu returnează nimic, și apoi spune ce nu dă bine. (Am postat mai sus cam cum văd eu că s-ar face problema asta )

[•Florian]

N-am încercat, dar cred că merge

Da, merge. Am facut-o eu mai demult si asa o rezolvasem.

@newsabbath: Ideea in sine e gresita. Poate de aceea nu da corect. Fa cum a zis MiÅŸu.

[•newsabbath]

Buna

Nu am inteles ce sa sciu in backul acela ...
Ce s afac distanta

Cod:

void back()
{
    if()
       {}
    else
         {
          for(int i=1;i<=5;i++)

}
}

nu stiu cum s ama apuc de problema asta ... m-am prins ca etse graf neorientat... backul, grafurile le invat de capul meu ... nu le-am facut inca ... multumesc de ajutor

Foloseste tag-ul [ code ] [/ code ] cand postezi cod. Exista un buton ajutator deasupra emoticoanelor. Nu posta consecutiv pe aceeasi tema, modifica mesajele anterioare.

[•Florian]

In back trebuie sa generezi permutari de 5 elemente. Pentru fiecare astfel de permutare, verifici daca ai solutie mai buna decat pana in momentul curent. Pe larg: O solutie canditata este data de o permutare ( s-o notam cu [p1,p2,p3,p4,p5] ). Acum, presupui ca Fat-Frumos se deplaseaza intai la a p1-a fata. De aici, pleaca spre cea de-a p2-a, apoi la a p3-a, apoi la a p4-a, apoi la a p5-a, iar apoi spre iesire. Aduni aceste distante, si vezi daca cumva e mai bine decat ai pana in momentul curent. Apoi, continui back-ul cu urmatoarea permutare, si repeti procedeul.

Totusi, iti recomand sa abandonezi pt moment problema, si sa inveti cu ce se mananca back-ul. Rezolva, de exemplu, probleme din arhiva educationala, precum Generare permutari, Combinari sau Submultimi.

Florian

[•newsabbath]

Backtrackingul l-am inteles ... stiu sa fac permutari, dar nu stiu cum sa pun  in solutie ...

Cod:

void back()
{
    if(k == n)
         //aici am vectorul sol... ce sa fac cu el aplic Dijkstra()... dar nu este acelasi???? disjkstra(ff, f[1]), dijkstra(f[1] , f[2] ) ...

    else
         for(int i=1;i<=n;i++)
             if(s[f[i]] == 0)
                {
                   s[f[i]] = 1;
                   sol[k] = f[i];
                   back(k+1);
                   s[f[i]] = 0;
                }

cum sa verific daca este buna solutia? care este criteriul? daca aplic o singura data Dijkstra nu obtin distanta minima la fiecare ... conteaza cum formez solutia de ce?
multumesc Florian!


am inceput sa ma prind;


dijkstra aplic de 5 ori, cate fete sunt, salvez distantele si vectorul tata pentru fiecare dintre acestea intr-o matrice; apoi fac backtracking pentru sirul feteleor si calculez distanta pt fata data ---ff, f1, f2, f3, f4, f5, si o camera din care ies pana gasesc suma minima



Editat de moderator: Foloseste [ code]...[/ code] cand postezi secvente de cod. Este a treia oara cand ti se atrage atentia asupra acestui lucru.