Pagini recente » Cod sursa (job #1671049) | Cod sursa (job #1259831) | Cod sursa (job #1700288) | Cod sursa (job #2777226) | Cod sursa (job #234946)
Cod sursa(job #234946)
#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);
}