Cod sursa(job #132826)

Utilizator marinMari n marin Data 6 februarie 2008 18:18:22
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#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;
}