Mai intai trebuie sa te autentifici.
Cod sursa(job #271850)
Utilizator | Data | 5 martie 2009 23:47:15 | |
---|---|---|---|
Problema | Sate | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.79 kb |
#include<stdio.h>
#define NM 30001
#define MM 100025
struct dist{int a,b,d;};
dist v[MM+1],w[MM+1];
int pv[NM+1],pw[NM+1];
int n,m,x,y,dxy;
int c[NM+1],li=1,ls,viz[NM+1],d[NM+1];
int cvida(){return li>ls;}
void pune(int x){c[++ls]=x,viz[x]=1;}
int scoate(){return c[li++];}
void poz1(int st, int dr,int &piv){
int i=st,j=dr,d=0;
dist aux;
while(i<j){
if(v[i].a>v[j].a||v[i].a==v[j].a&&v[i].b>v[j].b){
aux=v[i],v[i]=v[j],v[j]=aux,d=1-d;
}
i+=d,j-=1-d;
}
piv=i;
}
void qsrt1(int li,int ls){
int piv;
if(li<ls){
poz1(li,ls,piv);
qsrt1(li,piv-1);
qsrt1(piv+1,ls);
}
}
void poz2(int st, int dr,int &piv){
int i=st,j=dr,d=0;
dist aux;
while(i<j){
if(w[i].b>w[j].b||w[i].b==w[j].b&&w[i].a>w[j].a){
aux=w[i],w[i]=w[j],w[j]=aux,d=1-d;
}
i+=d,j-=1-d;
}
piv=i;
}
void qsrt2(int li,int ls){
int piv;
if(li<ls){
poz2(li,ls,piv);
qsrt2(li,piv-1);
qsrt2(piv+1,ls);
}
}
int main(){
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
int i,p,gata=0,z,u;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(i=1;i<=m;++i){
scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].d);
w[i]=v[i];
}
//qsrt1(1,m);
//qsrt2(1,m);
for(i=1;i<=m;++i){
p=v[i].a;
if(!pv[p]) pv[p]=i;
}
for(i=1;i<=m;++i){
p=w[i].b;
if(!pw[p]) pw[p]=i;
}
pune(x);/*
while(!gata&&!cvida()){
z=scoate();
i=pv[z];
if(i){
while(i<=m&&v[i].a==z){
u=v[i].b;
if(!viz[u]) {
pune(u);
if(u>z) d[u]=d[z]+v[i].d;
else d[u]=d[z]-v[i].d;
}
if(u==y) {dxy=d[u];gata=1;break;}
i++;
}
}
if(gata) break;
i=pw[z];
if(i){
while(i<=m&&w[i].b==z){
u=w[i].a;
if(!viz[u]) {
pune(u);
if(u>z) d[u]=d[z]+w[i].d;
else d[u]=d[z]-w[i].d;
}
if(u==y) {dxy=d[u];gata=1;break;}
i++;
}
}
} */
printf("%d",dxy);
return 0;
}