自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻_ AFO

搬运于2025-08-24 22:07:06，当前版本为作者最后更新于2019-07-02 10:07:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到不少大佬都用状压DP过的，

但是，

凭良心估计一下自己的实力，发现本蒟蒻并不会啊……

重新思考一下，设dis[i][j]表示从i到j的最短边（限制收集）的长度。N<=100,可以用floyd处理。

最后贪心一下，把有干草的点i按照dis[1][i]排序，从最小的开始选。

蒟蒻水平低，还望各位大佬斧正。

#include<cstdio>
#include<algorithm>
#define res register int
using namespace std;

const int inf=23333333;
int n,m,k;
int dis[110][110];
int a[110],b[110];

template<class T>
inline void read(T& v)
{
    char c=getchar();v=0;
    while(c<'0'||c>'9'){c=getchar();}
    while(c>='0'&&c<='9'){v=(v<<3)+(v<<1)+(c^'0');c=getchar();}
}

inline void floyd()
{	
	for(res i=1;i<=n;i++)dis[i][i]=inf;
	
	for(res t=1;t<=n;t++)
	 for(res i=1;i<=n;i++)
	  for(res j=1;j<=n;j++)
	  {
	  	  dis[i][j]=dis[j][i]=max(dis[i][j],min(dis[i][t],dis[t][j]));
			//考虑是否要从t点绕行（因为是无向图，且无次数限制，可以随便走） 
	  }
}

inline int solve()
{
	for(res i=1;i<=k;i++)b[i]=dis[1][a[i]];
	
	sort(b+1,b+k+1);
	
	int ans=0;
	
	for(res i=1;i<=k;i++)//贪心在这里 
	if(b[i]>ans)//当前已经拥有ans个，判断是否能够从这走。 
	{
		ans++;
	}
	
	return ans;
}

int main()
{	
	read(n),read(m),read(k);
	
	for(res i=1;i<=k;i++)
		read(a[i]);
	
	int x,y,w;
	for(res i=1;i<=m;i++)
	{
		read(x),read(y),read(w);
		dis[x][y]=dis[y][x]=max(dis[x][y],w);
	}
	
	floyd();
	
	printf("%d",solve());
	
	return 0;
}