题解 P3094

Harry27182 · 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;
}