Advertisement
Saleh127

Light OJ 1049 / DFS-BFS

Nov 1st, 2021
959
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-01-23.08.30
  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. bool v[105][105];
  12. vector<ll>g[1005];
  13. ll cost[105][105];
  14. ll ans,ans1;
  15.  
  16. void dfs(ll in)
  17. {
  18.      for(auto d:g[in])
  19.      {
  20.           if(!v[in][d])
  21.           {
  22.                ans+=cost[in][d];
  23.                ans1+=cost[d][in];
  24.  
  25.                v[in][d]=v[d][in]=1;
  26.  
  27.                dfs(d);
  28.           }
  29.      }
  30. }
  31.  
  32. ///for u and v - we can either go u to v or v to u
  33.  
  34. int main()
  35. {
  36.    ios_base::sync_with_stdio(0);
  37.    cin.tie(0);cout.tie(0);
  38.  
  39.  
  40.    test
  41.    {
  42.         ll n,m,i,j,k,l;
  43.  
  44.         cin>>n;
  45.  
  46.         while(n--)
  47.         {
  48.              cin>>j>>k>>l;
  49.  
  50.              g[j].push_back(k);
  51.              g[k].push_back(j);
  52.  
  53.              cost[j][k]=0;
  54.              cost[k][j]=l;
  55.         }
  56.  
  57.         ans=ans1=0;
  58.  
  59.         dfs(1);
  60.  
  61.         cout<<"Case "<<cs<<": "<<min(ans,ans1)<<nl;
  62.  
  63.         memset(v,0,sizeof v);
  64.  
  65.         for(i=0;i<105;i++) g[i].clear();
  66.  
  67.    }
  68.  
  69.  
  70.    get_lost_idiot;
  71. }
  72.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement