931 Trilant

[•raduzer]

Aici puteti discuta despre problema Trilant.

[•popoiu.george]

iau 0 si nu stiu de ce... Fac roy floyd, dupa care caut nodul pentru care costul trilantului este minim, dupa care refac drumul recursiv.

Evaluatorul spune ca nu refac drumul complet.. Puteti da un test mai mare? Pe testele care le dau eu merge.

[•toni2007]

iau 0 si nu stiu de ce... Fac roy floyd, dupa care caut nodul pentru care costul trilantului este minim, dupa care refac drumul recursiv.

Evaluatorul spune ca nu refac drumul complet.. Puteti da un test mai mare? Pe testele care le dau eu merge.

Tu faci Roy Floyd pe 100 000 de noduri ?

[•popoiu.george]

u faci Roy Floyd pe 100 000 de noduri ?

Nop, in problema se specifica ca 50% din teste au N<=1000, si intr-adevar, pe 8 teste iau Memory limit exceeded.

[•devilkind]

Roy floyd nu iti intra nici pentru N < 1000. Ti-ar trebui N < 100. (Roy Floyd e N^3). Vezi poate gresesti la reconstituire (acolo mi se pare ca ai putea gresi).

[•popoiu.george]

Ti-ar trebui N < 100. (Roy Floyd e N^3).

Pe 7 teste imi afiseaza ca nu reconstitui corect, si pe restul Memory exceeded si TLE, sa inteleg ca pe 7 teste N<100 ?

O sa mai verific la reconstituire ... 

[•devilkind]

Ti-ar trebui N < 100. (Roy Floyd e N^3).

Pe 7 teste imi afiseaza ca nu reconstitui corect, si pe restul Memory exceeded si TLE, sa inteleg ca pe 7 teste N<100 ?

O sa mai verific la reconstituire ... 

In cazul asta verifica implementarea de la Roy Floyd. Ceva nu ai facut bine. Nu ar fi trebuit sa iti intre in timp pe asa multe teste.

[•popoiu.george]

Nu ar fi trebuit sa iti intre in timp pe asa multe teste.

Nu intra . Era ceva gresit la reconstituire.

[•popoiu.george]

A tercut ceva timp, va mai aparea articol cu solutii la .com 2009?

[•mathboy]

Uite aici solutiile: http://infoarena.ro/dot-com/2009/solutii/runda-1.

[•popoiu.george]

Multumesc mult Dragos, nu l-am gasit in articole si am crezut ca nu este redactat.

[•Mitza444]

Iau 0p dar nu inteleg ce gresesc.Am facut un Dijkstra din fiecare nod A,B,C si am retinut distantele  minime in 3 vector da,db,dc si varful de pe unde s-a trecut pt. a ajunge in varful curent l-am retinut in pa,pb,pc.Am parcurs nodurile si am retinut cea mai mica suma da+db+dc(solutia) si nodul in care este suma minima pt. reconstituire.Pe exemplu merge bine,dar pe testele celelate primesc cost prea mare,drumurile au noduri comune,muchii invalide sau    Killed by signal 11.

Multumesc.

Sursa mea:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 4000000*10
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
                percolate(poz[aux.ff],d);
                p[aux.ff]=vfmin;
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin=inf,sum,ind,j;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
    for(i=1;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin)
            trmin=sum,ind=i;
    }
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pa[j];
	}while(j!=-1);
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pb[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pc[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
    fclose(stdout);
    return 0;
}

[•Mitza444]

Se poate sa-mi trimiteti unul din testele 18,19,20 fisierul in si out ?Orice modificare am facut tot Killed by signal 11(SIGSEGV) iau .(desi evaluatoru imi arata ca folosesc mai putina memorie ca la alte teste si nu vad nici o greseala)

[•wefgef]

Testele din arhivă nu se fac publice.

[•Mitza444]

Ok nu stiam ca testele nu se fac publice.
Am mai incercat sa gasesc greseala si cred ca este la reconstituirea drumului.Eu am atribuit -1 pozitiei nodul din care pornesc si la restul pozitiilor varful  din care s-a ajuns in nodul curent i.Exemplu pentru reconstituirea drumului din A am facut urmatoarea:

Cod:

j=ind;i=0;//ind e varful un suma distantelor e minima
	while(j!=pa[A]){//pa retine varful din care s-a ajuns in nodul i
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);

Daca in while in loc de j!=pa[A] care este -1 puneam j>0 nu mai luam  Killed by signal 11(SIGSEGV),dar luam ca drum trebuie sa se termine cu A,B sau C.Nu imi dau seama ce operatie  face reconstituirea incat sa ia  Killed by signal 11(SIGSEGV) pt. ca la memorie e ok.
Aici e sursa completa:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 100000000
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
				p[aux.ff]=vfmin;
                percolate(poz[aux.ff],d);
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin,sum,ind=0,j,k;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
	trmin=da[1]+db[1]+dc[1];ind=1;
    for(i=2;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin){
            trmin=sum;
			ind=i;
		}
    }
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	j=ind;i=0;
	while(j!=pa[A]){
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pb[B]){
		sol[++i]=j;
		j=pb[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pc[C]){
		sol[++i]=j;
		j=pc[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
    fclose(stdout);
    return 0;
}

[•tzipleatud]

Salut!

Costurile din Dijkstra pot ajunge destul de mari, tinand cont de faptul ca muchiile pot fi si 4*10^6, asa ca pune long long unde e nevoie si fa constanta INF mai mare (gen 5*10^11). Bafta!

[•Mitza444]

Multumesc foarte mult Tiplea Tudor!!!Am facut cum ai spus tu si am pus 5*10^11 la inf si a mers.
Totusi mi se pare ciudat ca merge deoarece mie pe Mingw nu-mi compileaza cu 5*10^11,pentru ca spune ca imi da error: integer constant is too large for "long" type,dar totusi pe site merge.
Multumesc inca o data nu mi-as fi dat seama niciodata.

[•lucian666]

  Salut
Am facut problema cu Dijkstra cu heap si iau doar 70 pct. cu 3 Drum invalid  .Am pus long long unde e nevoie insa nu stiu unde as putea gresi .
Vreo sugestie ceva?
Multumesc 

[•visanr]

Pune long long la set (unde ai costul), la iterator si in dijkstra unde faci int val = I->f, trebuie long long val = I->f. De asemenea, mai adauga 2 zero-uri la inf, e prea mica valoarea care ai pus-o. Cu aceste modificari vei lua 100. 

[•lucian666]

  Mersi mult Radu.Cu ajutorul observatiilor tale am luat 100

[•Fayed]

Imi poate da cineva si mie un exemplu mai mare sa vad ce nu imi merge ? Mie imi da costul prea mare.

[•Mihai22e]

Pe testul

Cod:

14 15
1 2 5
1 4 9
2 3 3
2 14 8
3 4 4
4 5 8
5 6 10
5 8 7
6 7 11
8 11 2
8 13 10
8 12 9
11 13 14
11 12 15
11 14 10

imi da (cu sursa de 100p)

Cod:

24
2 4 1 
3 4 3 2 
2 4 5 

[•Zenus]

       Imi poate spune si mie cineva ce gresesc la urmatoarea sursa?? (presupun ca gresesc la reconstituire dar nu stiu ce...) http://www.infoarena.ro/job_detail/1227621?action=view-source

[•japjappedulap]

Alta problema faina stricata din cauza limitelor. Voi nu vreti sa lasati problema curata, vreti s-o frecati cat mai tare cu tipuri de date care sa primeasca 100 din bulan. Gandesti ca va scarpinati la monitor sa mor io

[•klamathix]

Nu înțeleg la ce te referi. N-avem nicio intenție să stricăm nimic, nu trebuie să fii agresiv.