我的思路,枚举b,c,维护到他们的前三大的值,只有90,可以告诉我错哪里了吗
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2505;
const int maxm=20005;
int n,m,k;
ll s[maxn];
int head[maxm],tot;
struct node{
int v,nxt;
}kano[maxm];
inline void add_kano(int u,int v){
++tot;
kano[tot].nxt=head[u];
kano[tot].v=v;
head[u]=tot;
}
vector<int>kano2[maxn];
struct point{
ll v;
int u;
}P[maxn][3];
int vis[maxn],dis[maxn][maxn];
vector<int>Mid;
void bfs(int x){
memset(vis,0,sizeof vis);
queue<int>q;
q.push(x);
vis[x]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i(head[u]);i;i=kano[i].nxt){
int v=kano[i].v;
if(vis[v])continue;
dis[x][v]=dis[x][u]+1;
q.push(v);
vis[v]=1;
}
}
}
inline void update(int a,int b){
ll res=s[a]+s[b];
if(res>P[b][2].v){
P[b][2].v=res;
P[b][2].u=a;
}
sort(P[b],P[b]+3,[](const point A,const point B){
return A.v>B.v;
});
}
ll ans=0;
inline void get_ans(int b,int c){
for(int i(0);i<=2;++i){
for(int j(0);j<=2;++j){
if(P[b][i].v==-1||P[c][j].v==-1)continue;
if(P[b][i].u!=c&&P[b][i].u!=P[c][j].u&&P[c][j].u!=b&&P[c][j].u!=P[b][i].u)ans=max(ans,P[b][i].v+P[c][j].v);
}
}
}
int MMid[maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i(2);i<=n;++i){
cin>>s[i];
P[i][0].v=P[i][1].v=P[i][2].v=-1;
}
for(int i(1),u,v;i<=m;++i){
cin>>u>>v;
add_kano(u,v);
add_kano(v,u);
}
for(int i(1);i<=n;++i){
bfs(i);
for(int j(1);j<=n;++j){
if(i==j)continue;
if(dis[i][j]-1<=k)kano2[i].emplace_back(j);
}
}
for(int a:kano2[1]){
for(int b:kano2[a]){
if(b==1)continue;
if(a==b)continue;
update(a,b);
MMid[b]=1;
}
}
for(int i(2);i<=n;++i){
if(MMid[i])Mid.emplace_back(i);
}
for(int b:Mid){
for(int c:Mid){
if(b==c||dis[b][c]-1>k)continue;
get_ans(b,c);
}
}
cout<<ans;
return 0;
}
/*
8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
*/