AC了但有疑问
查看原帖
AC了但有疑问
1152799
wsy_I楼主2025/7/24 20:23

这是我的第 11 版代码:

#include<bits/stdc++.h>
#define N (int)(3e3+1e1)
using namespace std;
int n,m,dis1[N],dis2[N],dis3[N],u,v,s1,t1,s2,t2,ans=-1;
bool vis1[N],vis2[N],vis3[N];
vector<int> G[N];
struct D{int at,d;};
void bfs1(int x){
    memset(dis1,-1,sizeof(dis1));
    queue<D> q;
    q.push({x,0});
    vis1[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis1[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis1[G[t.at][i]]){
                vis1[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
void bfs2(int x){
    memset(dis2,-1,sizeof(dis2));
    queue<D> q;
    q.push({x,0});
    vis2[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis2[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis2[G[t.at][i]]){
                vis2[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
void bfs3(int x){
    memset(dis3,-1,sizeof(dis3));
    queue<D> q;
    q.push({x,0});
    vis3[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis3[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis3[G[t.at][i]]){
                vis3[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>s1>>t1>>s2>>t2;
    bfs1(1);
    bfs2(s1);
    bfs3(s2);
    for(int i=1;i<=n;i++){
        if(dis1[i]+dis2[i]<=t1 && dis1[i]+dis3[i]<=t2) ans=max(ans,m-(dis2[i]+dis3[i]+dis1[i]));
    }
    cout<<ans<<endl;
    return 0;
}

(bfs是从某题抄过来的
然后WA,20pts。
但是——

#include<bits/stdc++.h>
#define N (int)(3e3+1e1)
using namespace std;
int n,m,dis1[N],dis2[N],dis3[N],u,v,s1,t1,s2,t2,ans=-1;
bool vis1[N],vis2[N],vis3[N];
vector<int> G[N];
struct D{int at,d;};
void bfs1(int x){
    memset(dis1,0x3f,sizeof(dis1));
    queue<D> q;
    q.push({x,0});
    vis1[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis1[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis1[G[t.at][i]]){
                vis1[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
void bfs2(int x){
    memset(dis2,0x3f,sizeof(dis2));
    queue<D> q;
    q.push({x,0});
    vis2[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis2[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis2[G[t.at][i]]){
                vis2[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
void bfs3(int x){
    memset(dis3,0x3f,sizeof(dis3));
    queue<D> q;
    q.push({x,0});
    vis3[x]=true;
    while(!q.empty()){
        D t=q.front();
        q.pop();
        dis3[t.at]=t.d;
        for(int i=0;i<G[t.at].size();i++){
            if(!vis3[G[t.at][i]]){
                vis3[G[t.at][i]]=true;
                q.push({G[t.at][i],t.d+1});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>s1>>t1>>s2>>t2;
    bfs1(1);
    bfs2(s1);
    bfs3(s2);
    for(int i=1;i<=n;i++){
        if(dis1[i]+dis2[i]<=t1 && dis1[i]+dis3[i]<=t2) ans=max(ans,m-(dis2[i]+dis3[i]+dis1[i]));
    }
    cout<<ans<<endl;
    return 0;
}

我们只要把初始化的 1-1 改成 0x3f 就能过!

但是鉴于我用的是 BFS 求最短路所以初始化成什么应该没有区别吧。。。非常玄学,求大佬解答

2025/7/24 20:23
加载中...