| 123456 |
- #include <algorithm>
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m,k;cin>>n>>m>>k;++k;vector<long long>score(n);for(int i=1;i<n;++i)cin>>score[i];vector<vector<int>>g(n);while(m--){int u,v;cin>>u>>v;--u;--v;g[u].push_back(v);g[v].push_back(u);}vector<vector<char>>reach(n,vector<char>(n));for(int s=0;s<n;++s){vector<int>d(n,-1);queue<int>q;d[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();reach[s][u]=1;if(d[u]==k)continue;for(int v:g[u])if(d[v]<0)d[v]=d[u]+1,q.push(v);}}vector<vector<int>>best(n);for(int b=1;b<n;++b){for(int a=1;a<n;++a)if(a!=b&&reach[0][a]&&reach[a][b])best[b].push_back(a);sort(best[b].begin(),best[b].end(),[&](int x,int y){return score[x]>score[y];});if(best[b].size()>3)best[b].resize(3);}long long ans=0;for(int b=1;b<n;++b)for(int c=1;c<n;++c)if(b!=c&&reach[b][c])for(int a:best[b])for(int d:best[c])if(a!=c&&a!=d&&b!=d)ans=max(ans,score[a]+score[b]+score[c]+score[d]);cout<<ans<<'\n';}
|
