Advertisement
Guest User

Untitled

a guest
Jul 25th, 2017
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. const int MAXN = 1e5+5;
  8. int n,m,st,maxsize,idxnum[MAXN],level[MAXN],check[MAXN];
  9. vector<int> g[MAXN],direct[MAXN];
  10. void read_input(){
  11.     scanf("%d%d%d",&n,&m,&st);
  12.     for(int i = 1;i<=n;++i) scanf("%d",idxnum + i);
  13.     while(m--){
  14.         int a,b;
  15.         scanf("%d%d",&a,&b);
  16.         g[a].push_back(b);
  17.         g[b].push_back(a);
  18.     }
  19. }
  20.  
  21. void bfs(){
  22.     queue<int> Q;
  23.     Q.push(st);
  24.     check[st] = true;
  25.     while(!Q.empty()){
  26.         int idx = Q.front();
  27.         Q.pop();
  28.         for(auto now:g[idx]){
  29.             if(check[now]) continue;
  30.             check[now] = true;
  31.             level[now] = level[idx]+1;
  32.             Q.push(now);
  33.         }
  34.     }
  35. }
  36.  
  37. void trackmax(){
  38.     for(int i = 1;i<=n;++i){
  39.         direct[level[i]].push_back(idxnum[i]);
  40.         maxsize = max(maxsize,level[i]);
  41.     }
  42. }
  43.  
  44. long long solve(){
  45.     bfs();
  46.     trackmax();
  47.     priority_queue<int> Q;
  48.     long long sum = 0;
  49.     for(int i = maxsize;i >= 1;--i){
  50.         for(auto now:direct[i])Q.push(now);
  51.         if(!Q.empty() && Q.top()>=0){
  52.             sum += Q.top();
  53.             Q.pop();
  54.         }
  55.     }
  56.     return sum;
  57. }
  58.  
  59. int main(){
  60.     //freopen("r","r",stdin);
  61.     read_input();
  62.     printf("%lld\n",solve());
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement