优化哥成功优化60pts
原题链接：50000.[CSP-S 2022] 假期计划
2025-10-26 10:32:51
发布于：北京
10阅读
0回复
0点赞
爽了！！！！
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int maxxxx(ull a,ull b,ull c,ull d){
return max(a,max(b,max(c,d)));
}
ull n, m, k , ans=0;
ull s[2505];
int dp[2605][2505];
int main() {
cin >> n >> m >> k;
k++;
for(ull i=2;i<=n;i++)cin>>s[i];
memset(dp,0x3f,sizeof dp);
while(m--){
int x,y;
cin>>x>>y;
dp[x][y]=1;
dp[y][x]=1;
}
for (ull x = 1; x <= n; x++)
for (ull i = 1; i <= n; i++)
for (ull j = 1; j <= n; j++)
if(i!=j && i!=x && j!=x)
dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][j]);
for(ull a=2;a<=n;a++){
if(dp[1][a]>k)continue;
for(ull b=2;b<=n;b++){
if(max(dp[1][a],dp[a][b])>k)continue;
if(a==b)continue;
for(ull c=2;c<=n;c++){
if(max(dp[1][a],max(dp[a][b],dp[b][c]))>k)continue;
if(a==c || b==c)continue;
for(ull d=2;d<=n;d++){
if(a==d || b==d || c==d)continue;
if(maxxxx(dp[1][a],dp[a][b],dp[b][c],max(dp[c][d],dp[d][1]))>k)continue;
ans=max(ans,s[a]+s[b]+s[c]+s[d]);
}
}
}
}
cout<<ans;
return 0;
}
有帮助，赞一个