Cod sursa(job #209413)

Utilizator za_wolfpalianos cristian za_wolf Data 22 septembrie 2008 11:16:03
Problema Datorii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#define NMAX 51
int x[NMAX][NMAX],sol[NMAX],in,sf,a,b,c,w[NMAX],y[NMAX][NMAX],i,j,n,m,k,l,t,s,z[NMAX],q[NMAX*NMAX];
int main()
{
	freopen("kkt.in","r",stdin);
	freopen("kkt.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		x[a][++x[a][0]]=b;
		x[b][++x[b][0]]=a;
		if ((!y[a][b])||(y[a][b]>c))
			y[a][b]=c;
		if ((!y[b][a])||(y[b][a]>c))
			y[b][a]=c;
	}
	for (i=1;i<=s;i++)
		scanf("%d",&z[i]);
	in=1;
	sf=1;
	q[1]=1;
	while (in<=sf)
	{
		for (i=1;i<=x[q[in]][x[q[in]][0]];i++)
			if (!w[x[q[in]][i]]||w[x[q[in]][i]]>w[q[in]]+y[q[in]][x[q[in]][i]])
			{
				w[x[q[in]][i]]=w[q[in]]+y[q[in]][x[q[in]][i]];
				q[++sf]=x[q[in]][i];
			}
		in++;
	}
	for (i=1;i<=s;i++)
		if (w[z[i]]<=t)
			sol[++sol[0]]=i;
	printf("%d\n",sol[0]);
	for (i=1;i<=sol[0];i++)
		printf("%d\n",sol[i]);

	return 0;
}