fork(1) download
copy 
  1. /*
  2. 1                                                                                                                       4                                                                                                                       4                                                                                                                       0 1 20                                                                                                                  1 2 2                                                                                                                   2 3 8                                                                                                                   3 1 10
  3. */
  4.  
  5. //modified dijkstra for finding the weight of the minimum shortest path tree
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define ll long long
  9. //#define mod 100000000000
  10. vector<vector<pair<ll,ll>>> adj;
  11. vector<ll> par;//this is for dijkstra
  12. vector<ll> dist;//this is for dijkstra
  13. vector<ll> lastadded;
  14.  
  15. //this is for kruskal
  16. vector<ll> parent;
  17. vector<ll> siz;
  18. struct edge{
  19.     ll u;
  20.     ll v;
  21.     ll w;
  22.     edge(ll a,ll b,ll c):u(a),v(b),w(c)
  23.     {
  24.  
  25.     }
  26.     bool operator <(const edge& other)
  27.     {
  28.         return w<other.w;
  29.     }
  30. };
  31. vector<edge> edges;
  32. struct node
  33. {
  34.     ll vertex;
  35.     ll dist;
  36. //    ll lastadded;
  37.     //we dont need this last added in the nodes as we have made a last added vector
  38.     //we would update there
  39.     node(ll a=0,ll b=0):vertex(a),dist(b)
  40.     {
  41.  
  42.     }
  43. };
  44. void initialize(ll n)
  45. {
  46.     //this clumsy thing got error
  47.     adj.clear();
  48.     par.clear();
  49.     dist.clear();
  50.     edges.clear();
  51.     parent.clear();
  52.     parent.assign(n,0);
  53.     siz.clear();
  54.     adj.resize(n);
  55.     par.assign(n,0);
  56.     dist.assign(n,LONG_MAX);
  57.     lastadded.assign(n,LONG_MAX);
  58.     siz.assign(n,1);
  59.     for(ll i=0;i<n;i++)
  60.     {
  61.         parent[i]=i;//self parent
  62.     }
  63.  
  64. }
  65. //do we need to write the logic for lastadded in the pq..
  66. //because we are just extracting the min and for extracting
  67. //in pq even if the logic is with comparing just the dist...
  68. //we can make the last added change accordingly..
  69. bool operator<(const node& n1,const node& n2)
  70. {
  71.     return n1.dist>n2.dist;
  72. }
  73.  
  74. ll dijkstra(ll s,ll n)
  75. {
  76. //    priority_queue<node,vector<node>,cmp> pq;
  77.     priority_queue<node> pq;
  78.     node temp(s,0);
  79.     dist[s]=0;
  80.     //no change in lastadded for the source
  81.     //for evernode we have to update the parent and dist and lastadded
  82.     pq.push(temp);
  83.     while(!pq.empty())
  84.     {
  85.         temp=pq.top();
  86.         pq.pop();
  87.         ll u=temp.vertex;
  88.         for(auto p:adj[u])
  89.         {
  90.             ll v=p.first;
  91.             ll wei=p.second;
  92.             if(dist[v]>dist[u]+wei||((dist[v]==dist[u]+wei)&&lastadded[v]>wei))
  93.                 //this should work as next time when some node with greater would be picked then
  94.             {
  95.                 dist[v]=dist[u]+wei;
  96.                 lastadded[v]=wei;
  97.                 par[v]=u;//no need but still
  98.                 node tem(v,dist[v]);
  99.                 pq.push(tem);
  100.                 //tem is the node
  101.             }
  102.         }
  103.     }
  104.     //now just add the value in the last added array..
  105.     ll res=0;
  106.     for(ll i=1; i<n; i++)
  107.     {
  108. //        cout<<lastadded[i]<<" "<<i<<endl;
  109.         if(lastadded[i]==LONG_MAX){return -1;}
  110.         res+=lastadded[i];
  111. //        res%=mod;
  112.     }
  113.     return res;
  114. }
  115. ll fparent(ll i)
  116. {
  117.     if(i==parent[i])
  118.     {
  119.         return i;
  120.     }
  121.     return parent[i]=fparent(parent[i]);
  122. }
  123. void unionw(ll u,ll v)
  124. {
  125.     ll pu=fparent(u);
  126.     ll pv=fparent(v);
  127.     if(siz[pu]>siz[pv])
  128.     {
  129.         siz[pu]+=siz[pv];
  130.         parent[pv]=pu;
  131.         parent[v]=pu;
  132.     }
  133.     else{
  134.         siz[pv]+=siz[pu];
  135.         parent[pu]=pv;
  136.         parent[u]=pv;
  137.     }
  138. }
  139.  
  140. ll kruskal(ll n,ll m)
  141. {
  142.     ll cost=0;//this is to be outputted
  143.     for(ll i=0;i<m;i++)
  144.     {
  145.         ll u=edges[i].u;
  146.         ll v=edges[i].v;
  147.         ll w=edges[i].w;
  148.         if(fparent(u)!=fparent(v))
  149.         {
  150. //            cout<<"uv"<<u<<v<<endl;
  151.             unionw(u,v);
  152.             cost+=w;
  153. //            cost%=mod;
  154.         }
  155.     }
  156.  
  157.     return cost;
  158. }
  159. //there may be disconnected graphs as well
  160. int main()
  161. {
  162.     ll t;
  163.     cin>>t;
  164.     while(t--)
  165.     {
  166.  
  167.         ll n;
  168.         cin>>n;
  169.         ll m;
  170.         cin>>m;
  171.         initialize(n);
  172.         for(ll i=0; i<m; i++)
  173.         {
  174.  
  175.             ll a;
  176.             cin>>a;
  177.             ll b;
  178.             cin>>b;
  179.             ll w;
  180.             cin>>w;
  181.             edge e(a,b,w);
  182.             edges.push_back(e);
  183.             adj[a].push_back({b,w});
  184.             adj[b].push_back({a,w});
  185.         }
  186.         //source is said to be 0
  187. //        cout<<dijkstra(0,n)<<endl;
  188.         ll res1=dijkstra(0,n);
  189. //        cout<<res1<<endl<<flush;
  190.  
  191.  
  192.         //we have to make the nodes for the edges because kruskals apply on edges and not
  193.         //vertices
  194.         //first sort the edge vector
  195.         sort(edges.begin(),edges.end());
  196. //        for(auto i:edges)
  197. //        {
  198. //            cout<<i.w<<endl;
  199. //        }
  200.         if(res1<0)
  201.         {
  202.             cout<<"NO"<<endl;
  203.             continue;
  204.         }
  205.         ll res2=kruskal(n,m);
  206. //        cout<<res2<<endl;
  207.  
  208.         if(res1==res2)
  209.         {
  210.             cout<<"YES"<<endl;
  211.         }
  212.         else{
  213.             cout<<"NO"<<endl;
  214.         }
  215.     }
  216. }
  217.  
Runtime error #stdin #stdout #stderr 0s 4304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/LQZMug
language:
C++14 (gcc 8.3)
created:
4 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!