> #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;
> }

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