题解：CF2057E2 Another Exercise on Graphs (hard version)

· · 题解

注意到 w_1,w_2,\cdots, w_n 有单调性，因此可以考虑二分答案。

对于当前二分到的 i，将图中所有大于 w_i 的边设为 1，其余边设为 0，如果按照以上建图方式，a,b 两点间的最短路小于 k 则代表方案可行，可以二分更大的 i。

但是这样的话显然无法满足询问 q 的范围。由于 n 很小，因此可以用 Floyd 以 O(n^3) 预处理出对于每一个 i，a,b 两点间的最短路 d_{i,a,b}。

将所有边按照边权从小到大排序。对于经过的每一条边 (u,v,w)，用这条边更新当前时刻的最短路。容易发现随着 w_i 大小的增加，0 的数量时单调不降的，因此如果此时 u,v 间的最短路已经为 0，就没有必要更新了。

预处理 O(n^3)，每个询问 O(\log m)，总时间复杂度 O(n^3+q\log m)。

代码见下（其中包含部分 C++17 及 C++20 特性）。

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef tuple<ll,ll,ll> tup;
ll T,n,m,q,d[405][405][405];
/*注意这里不要对于每组数组都开一个 d 数组，会 MLE 的*/
void solve(){
    cin>>n>>m>>q;
    vector<ll>ans(n+1);
    vector<tup>e(m);
    for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)d[0][i][j]=1e9;
    for(ll i=1;i<=n;i++)d[0][i][i]=0;
    for(auto&[u,v,w]:e){
        cin>>u>>v>>w;
        d[0][u][v]=d[0][v][u]=1;
    }
    for(ll k=1;k<=n;k++){
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                d[0][i][j]=min(d[0][i][j],d[0][i][k]+d[0][k][j]);
            }
        }
    }
    ll cnt=0;
    ranges::sort(e,[](tup x,tup y){
        return get<2>(x)<get<2>(y);
    });
//  cout<<"---------------\n";
    for(auto [u,v,w]:e){
//      cout<<u<<" "<<v<<" "<<w<<endl;
        if(d[cnt][u][v]==0)continue;
        ans[++cnt]=w;
//      cout<<"cnt="<<cnt<<endl;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                d[cnt][i][j]=d[cnt-1][i][j];
            }
        }
        d[cnt][u][v]=0;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                d[cnt][i][j]=min(d[cnt][i][j],d[cnt][i][u]+d[cnt][v][j]);//这里是u和v 
                d[cnt][i][j]=min(d[cnt][i][j],d[cnt][i][v]+d[cnt][u][j]);
            }
        }
    }
    for(ll i=1,u,v,k;i<=q;i++){
        cin>>u>>v>>k;
        ll l=1,r=cnt,mid=(l+r)/2;
        while(l<=r){
            mid=(l+r)/2;
            if(d[mid][u][v]<=k-1)r=mid-1;
            else l=mid+1;
        }
        cout<<ans[l]<<" ";
//      cout<<"i="<<i<<": "<<ans[l]<<"\n";
    }
    cout<<endl;
//  cout<<endl<<"-----------------------\n"<<endl;
}
int main(){
    cin.tie(0),cout.tie(0)->sync_with_stdio(0);
    cin>>T;
    while(T--){
        solve();
    }
}