132 Distante

[•hitmann]

  incerc sa fac problema cu Dijkstra cu heapuri dar doar primul test e corect, la restul iau raspuns incorect, mi-am facut mai multe exemple si imi da bine, nu imi dau seama unde gresesc, la operatiile cu heap-ul sau unde... ca sa pot efectua Descreste_cheie(poz, val),cand relaxez, pastrez un vector id, id[i ]=pozitia in heap a nod-ului i,    . Ar putea cineva sa-mi dea un test si raspunsul   (cu care cat de cat se poate face debug)? ... i just don't get it...(stiu ca este si solutie O(V+E) dar e important si acest algoritm)
Anyone ? 

[•nimenia]

grafu e neorientat:)) eu am ncerkt sa o fac cu grafu orientat si...ghici ce! nu mi a mers. vz sa nu faci la fel:PP

[•c_e_manu]

Am si eu o intrebare... am incercat sa fac Dijkstra si dupa aceea sa verific daca da acelasi rezultat...si bineinteles ca iau TLE pe 9 teste ... Am incercat sa verific doar conditiile, dar iau WA atunci... probabil nu verific corect... imi poate da cineva un indiciu despre cum ar trebui? In ce moment trebuie sa verific aceste conditii??? Ms!

[•fireatmyself]

ai citit articolul cu solutii?
eu am luat 100 folosind Bellman Ford cu coada.

[•c_e_manu]

O sa incerc si solutia explicata in articol... Dupa aceea o sa ma documentez si depsre Bellman Ford...ca nu stiu in ce consta algoritmul Ms again!

[•avram_florin]

Poate cineva sa imi explice ce e gresit in rationamentul meu pentru ca iau doar 40 de puncte.Eu iau fiecare muchie din fisier si incerc sa vad daca pot obtine un drum mai scurt,adica x,y sunt capetele muchie,iar c costul si verific daca d

• +c<d[y]||d[y]+c<d
• ,iar daca e asa inseamna ca Bronzarel nu a calculat bine distanta minima.E ceva gresit in asta?

[•elfus]

Cand aveti timp, puteti mari limita de timp? Solutia O(T * (N + M)) ia doar 50 de puncte, iar sursa asta lua inainte 100: http://infoarena.ro/job_detail/787223?action=view-source . Multumesc.

[•klamathix]

Pai din cauza sursei aleia si altora in genul ei am schimbat limita. Sursa aia face dijkstra. Probabil era intr-adevar prea stransa, am mai pus 0.02  .
Daca tot nu merge, nu mai folosi STL, si nu fa operatii inutile. N-ai nevoie sa construiesti graful deloc aici. Ai nevoie doar sa parcurgi muchiile o data.

[•liana]

Cred ca limita de timp e prea mica. Iau 60 de puncte(cu tle pe testul 7) si nu stiu cum as mai putea optimiza. Am O(t*(n+m)).

[•vendetta]

Incearca sa parsezi citirea. S-a luat 100 de puncte chiar azi.

[•PetcuIoan]

Faptul ca c poate fi si 0 nu se prea vede in teste...

Edit: Nu m-am exprimat destul de clar, pe testul
4 3 1
0 1 2 1
1 3 2
1 2 7
2 4 0

una din solutiile oficiale ar raspunde DA, iar raspunsul este NU

[•Eby7]

Va rog frumos daca puteti sa ma ajutati putin. Am trimis o sursa care da 0 puncte. Treaba este ca, la primul test totul da bine si de la urmatoarele nu mai da corect. Cred ca are legatura cu folosirea succesiva a unor vectori. Oricum, daca imi puteti spune opinia voastra...

Asta e sursa

Cod:

#include<fstream>
#define inf 10001
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
struct muchie
{
    long x,y,c;
}q[100001];
long t;
long n,m,s,gasit;
long d[50001];
long v[50001];
int main()
{
    long x,y,c;
    long ok;
    f>>t;
    for(long k=1;k<=t;k++)
    {
        gasit=0;
        f>>n>>m>>s;
        for(long j=1;j<=n;j++)
         f>>v[j];
        for(long j=1;j<=m;j++)
        {
            f>>x>>y>>c;
            q[j].x=x;
            q[j].y=y;
            q[j].c=c;
            if(x==s)
             d[y]=c;
            if(y==s)
             d[x]=c;
        }
        for(long i=1;i<=n;i++)
         if(d[i]==0&&i!=s)
             d[i]=inf;
        do
        {
            ok=1;
            for(long i=1;i<=m;i++)
             if(d[q[i].y]>d[q[i].x]+q[i].c)
             {
                 d[q[i].y]=d[q[i].x]+q[i].c;
                 ok=0;
             }
        }while(!ok);
        /*for(long i=1;i<=n;i++)
         g<<d[i]<<" ";
        g<<"\n";*/
        for(long i=1;i<=n;i++)
          if(d[i]!=v[i])
           gasit=1;
        if(!gasit)
         g<<"DA"<<"\n";
        else
         g<<"NU"<<"\n";
    }
    return 0;
}

Foloseste tag-ul [ code ] [/ code ] cand postezi cod.

[•vladm97]

Vezi ca tu nu ai eliminat muchiile din graf. Fiecare nou graf va mosteni muchiile predecesorului sau. Am patit si eu aceeasi chestie.

[•SwissRhino]

Testele la problema aceasta sunt foarte proaste.
O solutie care verifica doar daca nu se pot face imbunatatiri ia 100 de puncte.

Cod:

 if (best[a] + c < best[b] || best[b] + c < best[a]) ok = false 

Asa ca va rog sa inlocuiti un test cu acest test

Cod:

2 1 1
0 0
1 2 1

PS: cred ca 5 din ultimele 6 surse de 100 sunt gresite.

[•theprdv]

Testele la problema aceasta sunt foarte proaste.
O solutie care verifica doar daca nu se pot face imbunatatiri ia 100 de puncte.

Cod:

 if (best[a] + c < best[b] || best[b] + c < best[a]) ok = false 

Asa ca va rog sa inlocuiti un test cu acest test

Cod:

2 1 1
0 0
1 2 1

asa e... nu sunt bune testele pentru ca nu e nici un test in care se verifica daca o distanta calculata de Bronzarica ala e mai mica decat cea corecta.. (adica verificam pentru toate nodurile daca se gaseste distanta calculata de Br.)

PS: cred ca 5 din ultimele 6 surse de 100 sunt gresite.