Cod sursa(job #204138)

Utilizator vlad.maneaVlad Manea vlad.manea Data 22 august 2008 09:44:21
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 32768

int *G[nmax], *D[nmax];
int deg[nmax], dist[nmax], viz[nmax];
int X, Y, N, M;

void parcour(int X)
{
	int i;

	if (viz[Y-1])
		return;

	for (i = 0; i < deg[X] && !viz[Y-1]; ++i)
		if (!viz[G[X][i]])
		{
			viz[G[X][i]] = 1;
			dist[G[X][i]] = dist[X] + D[X][i];
			parcour(G[X][i]);
		}
}

int main()
{
	int x, y, d, i;

	freopen("sate.in", "r", stdin);

	scanf("%d%d%d%d", &N, &M, &X, &Y);

	while (M--)
	{
		scanf("%d%d%d", &x, &y, &d);
		deg[x-1]++;
		deg[y-1]++;
	}

	for (i = 0; i < N; deg[i++] = 0)
	{
		G[i] = (int *)malloc(deg[i] * sizeof(int));
		D[i] = (int *)malloc(deg[i] * sizeof(int));
	}

	fseek(stdin, 0, SEEK_SET);

	scanf("%d%d%d%d", &N, &M, &X, &Y);

	while (M--)
	{
		scanf("%d%d%d", &x, &y, &d);

		if (x > y)
		{
			x = x+y;
			y = x-y;
			y = x-y;
		}

		G[x-1][deg[x-1]] = y-1;
		D[x-1][deg[x-1]] = d;
		deg[x-1]++;

		G[y-1][deg[y-1]] = x-1;
		D[y-1][deg[y-1]] = -d;
		deg[y-1]++;
	}

	viz[X-1] = 1;
	parcour(X-1);

	freopen("sate.out", "w", stdout);

	printf("%d\n", dist[Y-1]);

	return 0;

}