自动搬运

查看原文

来自洛谷，原作者为

	Harry27182 RESET。

搬运于2025-08-24 21:45:15，当前版本为作者最后更新于2020-12-31 18:46:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

又是一道大水题......

本题需要多源最短路。看到$n<=200$的范围，果断选择$Floyd$。

for(int l=1;l<=n;l++)
	 for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	    	if(f[i][j]>f[i][l]+f[l][j])f[i][j]=f[i][l]+f[l][j];
            

记得先枚举中转点啊

然后先把$sum$设成正无穷，然后逐一枚举$1-k$,更新$sum$. 如果$sum$为正无穷，那么可行方案$--$,否则$ans+=sum$. 就可以完美$ac$了！

完整代码如下：

#include<bits/stdc++.h>
#define int long long//不要忘了开long long 
using namespace std;
int n,m,k,q,u,v,w,ans,sum,a,b;
int f[205][205];
signed main()
{
	cin>>n>>m>>k>>q;
	memset(f,63,sizeof(f));
	for(int i=1;i<=n;i++)f[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		f[u][v]=min(f[u][v],w);
	}//初始化部分 
	for(int l=1;l<=n;l++)
	  for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	    	if(f[i][j]>f[i][l]+f[l][j])f[i][j]=f[i][l]+f[l][j];//弗洛伊德 
	int num=q;
	for(int i=1;i<=q;i++)
	{
		cin>>a>>b;
		sum=0x3f3f3f3f;
		for(int j=1;j<=k;j++)
		{
			sum=min(sum,f[a][j]+f[j][b]);
		}//枚举每一个中转 
		if(sum==0x3f3f3f3f)num--;//如果不通，方案-- 
		else ans+=sum;//否则加上最短路程 
	}
	cout<<num<<endl<<ans;
	return 0;
}