Cod sursa(job #9488)

Utilizator diac_paulPaul Diac diac_paul Data 27 ianuarie 2007 15:48:51
Problema Amenzi Scor 10
Compilator c Status done
Runda Unirea 2007, clasele 11-12 Marime 2.19 kb
#include <stdio.h>
#include <stdlib.h>

#define NMax 151
#define MMax 1501
#define TMax 3501
#define KMax 12001
#define PMax 8001

FILE *fin, *fout;

long n, m, k, p, x[MMax], y[MMax], c[MMax], or[PMax], tm[PMax];
long d[NMax], *v[NMax], *cost[NMax], tmax, profit[NMax][TMax];

long in, sf, co[NMax * NMax], ct[NMax * NMax], inc[NMax][TMax];
long b[NMax][TMax];

void read();
void vid();

void solve()
{
	long i;

	in = sf = 0;
	co[0] = 1;
	ct[0] = 0;
	inc[1][0] = 1;
	b[1][0] = 0;

	while (in <= sf)
	{
		// sunt in orasul co[in] la timpul ct[in]

		for (i = 0; i < d[co[in]]; i++)
			if ( b[co[in]][ct[in]] + profit[v[co[in]][i]][ct[in] + cost[co[in]][i]] > b[v[co[in]][i]] [ct[in] + cost[co[in]][i]] && ct[in] + cost[co[in]][i] <= tmax)
			{
				b[v[co[in]][i]] [ct[in] + cost[co[in]][i]] = b[co[in]][ct[in]] + profit[v[co[in]][i]][ct[in] + cost[co[in]][i]];

				if (!inc[v[co[in]][i]] [ct[in] + cost[co[in]][i]])
				{
					sf++;
					co[sf] = v[co[in]][i];
					ct[sf] = ct[in] + cost[co[in]][i];
				}
			}

		inc[co[in]] [ct[in]] = 0;
		in++;
	}
}

void afis();

int main()
{
	read();
	vid();
	solve();
	afis();

	return 0;
}

void read()
{
	long i, j, o, t, a;
	fin = fopen("amenzi.in", "rt");

	fscanf(fin, "%ld %ld %ld %ld", &n, &m, &k, &p);

	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%ld %ld %ld", &x[i], &y[i], &c[i]);
		d[x[i]]++;
		d[y[i]]++;
	}
	for (i = 1; i <= n; i++)
	{
		v[i] = (long*) calloc(d[i], sizeof(long));
		cost[i] = (long *) calloc(d[i], sizeof(long));
		d[i] = 0;
	}
	for (i = 0; i < m; i++)
	{
		v[x[i]][d[x[i]]] = y[i];
		cost[x[i]][d[x[i]]++] = c[i];

		v[y[i]][d[y[i]]] = x[i];
		cost[y[i]][d[y[i]]++] = c[i];
	}

	for (i = 0; i < k; i++)
	{
		fscanf(fin, "%ld %ld %ld", &o, &t, &a);
		profit[o][t] += a;
	}

	for (i = 0; i < p; i++)
	{
		fscanf(fin, "%ld %ld", &or[i], &tm[i]);
		if (tm[i] > tmax) tmax = tm[i];
	}
	fclose(fin);
}

void vid()
{
	long i, j;

	for (i = 1; i <= n; i++)
		for (j = 0; j <= tmax; j++) b[i][j] = -1;
}

void afis()
{
	long i;
	fout = fopen("amenzi.out", "wt");

	for (i = 0; i < p; i++)
		fprintf(fout, "%ld\n", b[or[i]] [tm[i]]);

	fclose(fout);
}