Advertisement
Saleh127

Light OJ 1257 / BFS

Nov 11th, 2021
726
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-12-00.52.07
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. vector<ll>g[30005],cost[30005];
  13.  
  14. ll dis[30005],dis1[30005];
  15. bool v[30005];
  16.  
  17. ll bfs(ll u)
  18. {
  19.      queue<ll>q;
  20.  
  21.      memset(dis,0,sizeof dis);
  22.      memset(v,0,sizeof v);
  23.  
  24.      v[u]=1;
  25.      dis[u]=0;
  26.  
  27.      q.push(u);
  28.  
  29.      ll ans=0ll,node,d;
  30.  
  31.      while(q.empty()==false)
  32.      {
  33.           d=q.front();
  34.           q.pop();
  35.  
  36.           if(dis[d]>ans)
  37.           {
  38.                ans=dis[d];
  39.                node=d;
  40.           }
  41.  
  42.           for(ll i=0;i<g[d].size();i++)
  43.           {
  44.                ll dd=g[d][i];
  45.  
  46.                if(v[dd]==0)
  47.                {
  48.                     v[dd]=1;
  49.                     dis[dd]=dis[d]+cost[d][i];
  50.                     q.push(dd);
  51.                }
  52.           }
  53.      }
  54.  
  55.      return node;
  56. }
  57.  
  58. void bfs1(ll u)
  59. {
  60.      queue<ll>q;
  61.  
  62.      memset(dis1,0,sizeof dis1);
  63.      memset(v,0,sizeof v);
  64.  
  65.      v[u]=1;
  66.      dis1[u]=0;
  67.  
  68.      q.push(u);
  69.  
  70.      ll ans=0ll,node,d;
  71.  
  72.      while(q.empty()==false)
  73.      {
  74.           d=q.front();
  75.           q.pop();
  76.  
  77.           for(ll i=0;i<g[d].size();i++)
  78.           {
  79.                ll dd=g[d][i];
  80.  
  81.                if(v[dd]==0)
  82.                {
  83.                     v[dd]=1;
  84.                     dis1[dd]=dis1[d]+cost[d][i];
  85.                     q.push(dd);
  86.                }
  87.           }
  88.      }
  89. }
  90.  
  91.  
  92. int main()
  93. {
  94.    ios_base::sync_with_stdio(0);
  95.    cin.tie(0);cout.tie(0);
  96.  
  97.    ///3 bfs for farthest node from every node
  98.  
  99.    test
  100.    {
  101.         ll n,m,i,j,k,l;
  102.  
  103.         cin>>n;
  104.  
  105.         for(i=0;i<n-1;i++)
  106.         {
  107.              cin>>j>>k>>l;
  108.  
  109.              g[j].push_back(k);
  110.              g[k].push_back(j);
  111.              cost[j].push_back(l);
  112.              cost[k].push_back(l);
  113.         }
  114.  
  115.         k=bfs(0ll);
  116.  
  117.         l=bfs(k);
  118.  
  119.         bfs1(l);
  120.  
  121.         cout<<"Case "<<cs<<":"<<nl;
  122.  
  123.         for(i=0;i<n;i++)
  124.         {
  125.              cout<<max(dis[i],dis1[i])<<nl;
  126.         }
  127.  
  128.  
  129.         for(i=0;i<n+2;i++)
  130.         {
  131.              g[i].clear();
  132.              cost[i].clear();
  133.         }
  134.  
  135.    }
  136.  
  137.  
  138.    get_lost_idiot;
  139. }
  140.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement