Cod sursa(job #234946)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 22 decembrie 2008 12:14:20
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>

struct nod{int x,c;nod *urm;};
struct cod{int x;cod*urm;};
nod *A[30001];
cod *que,*ultim;
int drum[30001];

void ad(int x,int y,int c)
{
nod *urm;
urm = new nod;
urm->x = y;
urm->c = c;
urm->urm = A[x];
A[x] = urm;
}

void add(int x)
{
cod *urm;
urm = new cod;
urm->x = x;
urm->urm= NULL;
if (que==NULL) que=urm,ultim=que;
else ultim->urm = urm,ultim = urm;
}

void BFS()
{
nod *w;
cod *scos;
while (que!=NULL)
{
w = A[que->x];
while (w!=NULL)
{
if (drum[w->x]==0) if (que->x>w->x) drum[w->x] = drum[que->x]-w->c,add(w->x);
                   else drum[w->x] = drum[que->x]+w->c,add(w->x);
w = w->urm;
}
scos = que;
que = que->urm;
delete scos;
}
}

int main()
{
FILE *in = fopen("sate.in","r");
FILE *out = fopen("sate.out","w");

int n,m,X,Y,x,y,c;

fscanf(in,"%d%d%d%d",&n,&m,&X,&Y);

while (m)
{
m--;
fscanf(in,"%d%d%d",&x,&y,&c);
ad(x,y,c);
ad(y,x,c);
}

add(X);
drum[X]=-1;
BFS();
if (drum[Y]<0) fprintf(out,"%d",-drum[Y]+1);
else fprintf(out,"%d",drum[Y]+1);
}