fork download
copy 
  1. /*
  2. AUTHOR : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #include<stdio.h>
  9. using namespace std;
  10.  
  11. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  12. #define MAX 100050
  13.  
  14. #define ll long long
  15. #define ld long double
  16. #define lli long long int
  17.  
  18. #define pb emplace_back
  19. #define INF 1000000000
  20. #define mod 1000000007
  21.  
  22. // trignometric function always give value in Radians only
  23. #define PI acos(-1) //3.1415926535897932384626433832795028
  24. #define dsin(degree) sin(degree*(PI/180.0))
  25. #define dcos(degree) cos(degree*(PI/180.0))
  26. #define dtan(degree) tan(degree*(PI/180.0))
  27.  
  28. #define rsin(radian) sin(radian)
  29. #define rcos(radian) cos(radian)
  30. #define rtan(radian) tan(radian)
  31.  
  32. #define loop(i,n) for (lli i = 0; i < n; i++)
  33. #define loopitr(xt,vec) for (auto xt : vec)
  34. #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  35. #define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
  36. #define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
  37. #define itr :: iterator it
  38. #define WL(t) while(t --)
  39.  
  40. #define all(v) v.begin(),v.end()
  41. #define rall(v) v.rbegin(),v.rend()
  42. #define sz(x) int(x.size())
  43. #define F first
  44. #define S second
  45.  
  46. #define mii map<lli,lli>
  47. #define vi vector<lli>
  48. #define seti set<lli>
  49. #define pii pair<lli,lli>
  50.  
  51. #define gcd(a,b) __gcd((a),(b))
  52. #define lcm(a,b) (a/gcd(a,b))*b
  53. #define abs(x) ((x < 0)?-(x):x)
  54.  
  55. #define endl '\n'
  56.  
  57. template <typename T>
  58. void print(T x){cout<<x<<endl;}
  59. template <typename T1, typename T2>
  60. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  61. template <typename T1, typename T2,typename T3>
  62. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  63.  
  64. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  65. #define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  66.  
  67. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  68. #define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  69. #define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
  70.  
  71. #define FD(N) fixed<<setprecision(N)
  72.  
  73. #define deb(x) cout<<#x<<" "<<x<<endl;
  74.  
  75. // chandan1,2
  76. void chandan1(){int y=1;return;}
  77. void chandan2(){
  78.         loop(i,10){
  79.         lli x=1;
  80.     }
  81.     return(chandan1());
  82. }
  83.  
  84. int main(){
  85. fastio
  86. lli t=1;
  87. //cin>>t;
  88. chandan2();
  89. while(t--) {
  90.     lli n , m , k , s;
  91.     cin>>n>>m>>k>>s;
  92.     lli a[n+1];
  93.     vi same[n+1];
  94.     FOR(i,1,n+1){
  95.         cin>>a[i];
  96.         same[a[i]].pb(i);
  97.     }
  98.  
  99.     vi adj[n+1];
  100.  
  101.     loop(i,m){
  102.         lli x,y;
  103.         cin>>x>>y;
  104.         adj[x].pb(y);
  105.         adj[y].pb(x);
  106.     }
  107.  
  108.     /*
  109.     Now do multisource BFS from all nodes (having same a[i] ) and find shortest distance to other node
  110.     
  111.     in first example after doing multisource_BFS from same valued nodes our 2-D matrix be like -
  112.     
  113.         1   2   3   4   5 <-- node number
  114.  
  115.     1 -  0   1   2   1   2
  116.  
  117.     2 -  1   0   1   1   0
  118.  
  119.     3 -  1   2   1   0   1
  120.   
  121.     4 -  2   1   0   1   2 
  122.     
  123.     ^
  124.     |
  125.     |
  126.     
  127.     type of goods  
  128.     
  129.     
  130.     Now we have to sort this column wise as we need "s" different products with minimum distance after that print 
  131.     sum of top s values from each coulumn -
  132.     
  133.     after sorting
  134.     
  135.                          1   2   3   4   5 <-- node number
  136.                 
  137.                          0   0   0   0   0
  138.                 
  139.                          1   1   1   1   1
  140.                 
  141.                          1   1   1   1   2
  142.                   
  143.                          2   2   2   1   2 
  144.          
  145. sum top s elemnt =       2   2   2   2   3
  146.     
  147.     */
  148.  
  149.     lli dist[k+1][n+1];
  150.  
  151.     vi ans_cost[n+1];
  152.  
  153.     for(lli type = 1; type<=k;type++)
  154.     {
  155.         bool vis[n+1]={0};
  156.         queue<lli>q;
  157.         // multipsource BFS
  158.         for(auto xt : same[type])
  159.         {
  160.             q.push(xt);
  161.             vis[xt]=1;
  162.             dist[type][xt] = 0;
  163.         }
  164.  
  165.         while(!q.empty())
  166.         {
  167.             lli parent = q.front();
  168.             q.pop();
  169.  
  170.             for(auto child : adj[parent])
  171.             {
  172.                 if(!vis[child])
  173.                 {
  174.                     vis[child]=1;
  175.                     q.push(child);
  176.                     dist[type][child]=dist[type][parent]+1;
  177.                 }
  178.             }
  179.         }
  180.  
  181.         for(lli node = 1; node<=n;node++)
  182.             ans_cost[node].pb(dist[type][node]);
  183.  
  184.     }
  185.  
  186.     // for(lli i=1;i<=k;i++)
  187.     // {
  188.     //     for(lli j =1;j<=n;j++)
  189.     //     {
  190.     //         cout<<dist[i][j]<<" ";
  191.     //     }
  192.     //     cout<<endl;
  193.     // }
  194.  
  195.     for(lli i=1;i<=n;i++)
  196.     {
  197.         sort(all(ans_cost[i]));
  198.  
  199.         lli sum= 0 ;
  200.  
  201.         loop(j,s)
  202.             sum+=ans_cost[i][j];
  203.  
  204.         cout<<sum<<" ";
  205.     }
  206.  
  207.  
  208.  
  209.   }
  210.  
  211. return 0;
  212. }
  213.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
stdout
copy 
2 2 2 2 3
https://ideone.com/yKOojg
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!