Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <queue>
- using namespace std;
- const int MAXN = 1e5+5;
- int n,m,st,maxsize,idxnum[MAXN],level[MAXN],check[MAXN];
- vector<int> g[MAXN],direct[MAXN];
- void read_input(){
- scanf("%d%d%d",&n,&m,&st);
- for(int i = 1;i<=n;++i) scanf("%d",idxnum + i);
- while(m--){
- int a,b;
- scanf("%d%d",&a,&b);
- g[a].push_back(b);
- g[b].push_back(a);
- }
- }
- void bfs(){
- queue<int> Q;
- Q.push(st);
- check[st] = true;
- while(!Q.empty()){
- int idx = Q.front();
- Q.pop();
- for(auto now:g[idx]){
- if(check[now]) continue;
- check[now] = true;
- level[now] = level[idx]+1;
- Q.push(now);
- }
- }
- }
- void trackmax(){
- for(int i = 1;i<=n;++i){
- direct[level[i]].push_back(idxnum[i]);
- maxsize = max(maxsize,level[i]);
- }
- }
- long long solve(){
- bfs();
- trackmax();
- priority_queue<int> Q;
- long long sum = 0;
- for(int i = maxsize;i >= 1;--i){
- for(auto now:direct[i])Q.push(now);
- if(!Q.empty() && Q.top()>=0){
- sum += Q.top();
- Q.pop();
- }
- }
- return sum;
- }
- int main(){
- //freopen("r","r",stdin);
- read_input();
- printf("%lld\n",solve());
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement