3058296_ac_15ms_1132k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf 2100000000

using namespace std;

int f, p, c, m;
int map[501][501];
int dis[501], mark[501];
vector <int> ans;

void solve()
{
	int i, j, v, min;

	for(i = 0; i < f; i++)
	{
		dis[i] = inf;
		mark[i] = 0;
	}
	dis[0] = 0;
	for(i = 0; i < f; i++)
	{
		min = inf;
		for(j = 0; j < f; j++)
		{
			if(!mark[j]&&dis[j]<min)
			{
				min = dis[j];
				v = j;
			}
		}
		mark[v] = 1;
		for(j = 0; j < f; j++)
		{
			if(map[v][j]&&dis[v]+map[v][j]<dis[j])
			{
				dis[j] = dis[v]+map[v][j];
			}
		}
	}
}

int main()
{
	int i;
	int a, b, c, w;

	scanf("%d%d%d%d",&f,&p,&c,&m);
	memset(map,0,sizeof(map));
	for(i = 0; i < p; i++)
	{
		scanf("%d%d%d",&a,&b,&w);
		a--,b--;
		if(map[a][b]==0||map[a][b]>w)
		{
			map[a][b] = map[b][a] = w;
		}
	}
	solve();
	for(i = 0; i < c; i++)
	{
		scanf("%d",&a);
		a--;
		if(dis[a]<=m)
		{
			ans.push_back(i+1);
		}
	}
	printf("%d\n",ans.size());
	for(i = 0; i < ans.size(); i++)
		printf("%d\n",ans[i]);
	return 0;
}