Pagini recente » Cod sursa (job #722418) | Cod sursa (job #2400438) | Cod sursa (job #1576663) | Cod sursa (job #63380) | Cod sursa (job #132826)
Cod sursa(job #132826)
#include <stdio.h>
#define DIM 250001
struct nod {
int p;
int v;
nod *adr;
};
nod *v[DIM],*q;
int c[DIM];
char viz[DIM];
int n,m,x,y,i,ii,jj,kk,kMax,a,b;
int parc(int k) {
int i;
for (i=1;i<=n;i++)
viz[i]=0;
int p=1;
int u=1;
viz[x]=1;
c[1]=x;
while (p<=u) {
q = v[c[p]];
while (q!=NULL) {
if ((q->p<=k)&&(viz[q->v]==0)) {
u++;
c[u]=q->v;
viz[q->v]=1;
if (q->v==y) {
return 1;
}
}
q = q->adr;
}
p++;
}
return 0;
}
int main(){
kMax = -1;
FILE *f = fopen("pscnv.in","r");
fscanf(f,"%d %d %d %d",&n,&m,&x,&y);
for (i=1;i<=n;i++)
v[i]=NULL;
for (i=1;i<=m;i++) {
fscanf(f,"%d %d %d",&ii,&jj,&kk);
if (kk>kMax) {
kMax = kk;
}
q = new nod;
q->v = ii;
q->p=kk;
q->adr = v[jj];
v[jj]=q;
q = new nod;
q->v = jj;
q->p=kk;
q->adr = v[ii];
v[ii]=q;
}
fclose(f);
a=1;
b=kMax;
while (a<=b) {
m = (a+b)/2;
if (parc(m))
b=m-1;
else
a=m+1;
}
FILE *g = fopen("pscnv.out","w");
fprintf(g,"%d",a);
fclose(g);
return 0;
}