#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int map[505][505];
int n,m,d[505],q[50000005],inq[505],path[505];
void spfa()
{
	int i;
	for(i=1;i<=n;i++)
		d[i]=1000000000;
	int rear=0,front=0;
	q[0]=1;
	d[1]=0;
	while(rear>=front)
	{
		int u=q[front];
		inq[u]=0;
		for(i=1;i<=n;i++)
			if(map[u][i]!=0&&d[i]>d[u]+map[u][i])
			{
				d[i]=d[u]+map[u][i];
				path[i]=u;
				if(!inq[i])
				{
					inq[i]=1;
					q[++rear]=i;
				}
			}
		++front;
	}
}

int main()
{
	int f,p;
	while(scanf("%d%d%d%d",&n,&m,&f,&p)!=EOF)
	{
		int i,a,b,c;
		memset(map,0,sizeof(map));
		memset(inq,0,sizeof(inq));
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			map[a][b]=c;
			map[b][a]=c;
		}
		spfa();
		int x,h[105],j=0;
		for(i=1;i<=f;i++)
		{
			scanf("%d",&x);
			if(d[x]<=p)
				h[j++]=i;
		}
		printf("%d\n",j);
		for(i=0;i<j;i++)
			printf("%d\n",h[i]);
	}
	return 0;
}

• Re:不知道wa的原因 (50) 090609103 2011-10-18 23:00:23