关于 RE 的性质
查看原帖
关于 RE 的性质
299883
HYdroKomide楼主2022/11/27 16:56

RT,以下这段代码在 IDE 能够正常运行,并且过了样例,然而评测一片 RE(

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<utility>
using namespace std;
const int N=2510;
int n,m,k,dis[N][N];
long long val[N],ans;
vector<int>g[N];
set<pair<long long,long long> >p[N];
int bfs(int s){
    queue<int>q;
    while(!q.empty())q.pop();
    q.push(s);
    dis[s][s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(dis[s][u]+1<dis[s][v]){
            	dis[s][v]=dis[v][s]=dis[s][u]+1;
            	q.push(v);
			}
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=2;i<=n;i++)scanf("%lld",&val[i]);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++)bfs(i);
    for(int i=2;i<=n;i++)
    	for(int j=2;j<=n;j++){
    	    if(i==j)continue;
			if(dis[i][j]<=k+1&&dis[1][j]<=k+1)p[i].insert(make_pair(val[j],j));
			if(p[i].size()>3)p[i].erase(p[i].begin());
		}
	for(int i=2;i<=n;i++)
		for(int j=2;j<=n;j++)
			if(i!=j&&dis[i][j]<=k+1)
				for(auto s:p[i])
					if(s.second!=i&&s.second!=j)
						for(auto t:p[j])
							if(t.second!=i&&t.second!=j&&t.second!=s.second)
								ans=max(ans,val[s.second]+val[i]+val[j]+val[t.second]);
    printf("%lld\n",ans);
    return 0;
}

所以具体是怎么回事

2022/11/27 16:56
加载中...