1 条题解

  • 0
    @ 2023-6-21 20:06:08

    C++ :

    #pragma GCC optimize ("O2")
    #include <bits/stdc++.h>
    #define inf 0x3f3f3f3f
    #define met(a,b) memset(a,b,sizeof a)
    #define pb push_back
    #define mp make_pair
    #define rep(i,l,r) for(int i=(l);i<=(r);++i)
    #define inf 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    const int N = 1e3+50;;
    const int M = 6e5;
    const int mod = 19260817;
    const int mo=123;
    const double pi= acos(-1.0);
    typedef pair<int,int>pii;
    int n,m,S,T;
    ll dis[N],dp[2][N];
    int vis[N],mark[N];
    vector<pii>edg[N];
    ll spfa(int s,int t,ll x){
        for(int i=0;i<N;i++)dis[i]=1e18,vis[i]=0;
        queue<int>q;
        vis[s]=1;
        dis[s]=0;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=0;i<edg[u].size();i++){
                int v=edg[u][i].first;
                int w=edg[u][i].second;
                if(!mark[v])continue;
                if(dis[v]>dis[u]+x+w){
                    dis[v]=dis[u]+x+w;
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
    
        return dis[t];
    }
    void spfa2(int s,ll x){
        int ty=(s==S);
        for(int i=0;i<N;i++)dp[ty][i]=1e18,vis[i]=0;
        queue<int>q;
        vis[s]=1;
        dp[ty][s]=0;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=0;i<edg[u].size();i++){
                int v=edg[u][i].first;
                int w=edg[u][i].second;
                if(dp[ty][v]>dp[ty][u]+x+w){
                    dp[ty][v]=dp[ty][u]+x+w;
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
    }
    bool check(ll x){
        //x=3;
        ll len1=spfa(S,T,x);
        spfa2(S,x);
        spfa2(T,x);
        ll len2=1e18;
        for(int i=1;i<=n;i++){
            if(mark[i])continue;
            //printf("%lld %lld\n",dp[1][i],dp[0][i]);
            len2=min(len2,dp[1][i]+dp[0][i]);
        }
        //printf("len1:%lld len2:%lld\n",len1,len2);
       // system("pause");
        if(len1>len2)return false;
        return true;
    }
    int main(){
        int TT;
        scanf("%d",&TT);
        while(TT--){
            met(mark,0);
            for(int i=0;i<N;i++)edg[i].clear();
            scanf("%d%d%d%d",&n,&m,&S,&T);
            while(m--){
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                edg[u].pb(mp(v,w));
                edg[v].pb(mp(u,w));
            }
            int k;
            scanf("%d",&k);
            while(k--){
                int u;
                scanf("%d",&u);
                mark[u]=1;
            }
            ll l=0,r=1e15,ans=-1;
            while(l<=r){
                ll mid=(l+r)/2;
               //printf("mid:%lld\n",mid);
                if(check(mid))l=mid+1,ans=mid;
                else r=mid-1;
            }
            if(ans==-1)puts("Impossible");
            else if(ans==1e15)puts("Infinity");
            else {
                ll res=ans;
                for(int i=1;i<=5;i++){
                    if(check(res+i))ans=res+i;
                }
                printf("%lld\n",ans);
            }
        }
        return 0;
    }
    
    • 1

    #6075. 「2017 山东一轮集训 Day6」重建

    信息

    ID
    1031
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者