#include "iostream"
#include "map"
#include "set"
using namespace std;

int f,p,c,m;

void solve()
{
	const int max = 0x7fffffff;
	map<int,int> maps;
	set<int> s;
	int a[501][501];
	bool flag[501] = {false};
	int len[501];
    int i,j;
	int l,r,tm;

	for (i=0; i<501; i++)
	{
		len[i] = max;
		for (j=0; j<501; j++)
			a[i][j] = max;
	}
	for (i=1; i<=p; i++)
	{
		cin >> l >> r >> tm;
		a[l][r] = tm;
		a[r][l] = tm;
	}
	for (i=1; i<=c; i++)
	{
		cin >> l;
		maps.insert(pair<int,int>(l,i));
	}
	len[1] = 0;
	flag[1] = true;
	for (i=2; i<=f; i++)
		len[i] = a[1][i];
	while (true)
	{
		l = 0x7fffffff;
		for (i=2; i<=f; i++)
			if (flag[i] == false && len[i] < l)
			{
				l = len[i];
				r = i;
			}
		if (l > m)
			break;
		flag[r] = true;
		for (i=2; i<=f; i++)
		{
			if (flag[i] == false && len[r]+a[r][i] < len[i] && a[r][i] != 0x7fffffff)
			{
				len[i] = len[r]+a[r][i];
			}
		}
	}
	for (i=1; i<=f; i++)
		if (len[i] <= m)
		{
			map<int,int>::iterator q = maps.find(i);
			if (q != maps.end())
				s.insert(q->second);
		}
	
	cout << s.size() << endl;
	for (set<int>::iterator q=s.begin(); q!=s.end(); q++)
		cout << *q << endl;
}

int main()
{
	//freopen("s.txt","r",stdin);
	
	while (cin >> f >> p >> c >> m)
		solve();
	return 0;
}

• 考虑重边 (1486) zhao0057 2006-09-01 13:33:06
  • Re:考虑重边 (141) carew 2006-09-02 10:07:31
    • Re:考虑重边 (170) phoenixzz 2007-07-20 10:34:48