Source code for submission s1268

Go to diff to previous submission

spider.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. using namespace std;
  7.  
  8. int total_length;
  9. bool connected[2001];
  10.  
  11. struct Edge
  12. {
  13.   int v1,v2,l;
  14.   Edge(int from,int to,int length)
  15.   {
  16.     v1=from;v2=to;l=length;
  17.   }
  18. };
  19.  
  20. bool cmpE(const Edge &e1, const Edge &e2)
  21. {
  22.   return e1.l < e2.l;
  23. }
  24.  
  25. vector<Edge> edges;
  26.  
  27. void print_edges(const vector<Edge> &edges)
  28. {
  29.   for(int i = 0; i < edges.size(); i++)
  30.     cout << edges[i].l << ',';
  31.   cout << endl;
  32. }
  33.  
  34. void AddToG(const Edge &e)
  35. {
  36.   total_length += e.l;
  37.   connected[e.v1] = true;
  38.   connected[e.v2] = true;
  39. }
  40.  
  41. int FindEdge(int vertex)// najdu prvni hranu s timto uzlem k jiz pripojenymu uzlu
  42. {
  43.   for(int i = 0, im = edges.size(); i < im; i++)
  44.   {
  45.     if(edges[i].v1 == vertex)
  46.     {
  47.       if(connected[edges[i].v2])
  48.         return i;
  49.     }
  50.     else if(edges[i].v2 == vertex)
  51.     {
  52.       if(connected[edges[i].v1])
  53.         return i;
  54.     }
  55.   }
  56.   return -1;
  57. }
  58.  
  59. int main()
  60. {
  61.   bool disconnected;
  62.   int N,M,v1,v2,l;
  63.   //
  64.   while(1)
  65.   {
  66.     cin >> N >> M;
  67.     if(cin.eof()) break;
  68.     //
  69.     edges.clear();
  70.     memset(connected,0,2001);
  71.     total_length = 0;
  72.     disconnected = false;
  73.     //
  74.     for(int m = 0; m < M; m++)
  75.     {
  76.       cin >> v1 >> v2 >> l;
  77.       edges.push_back(Edge(v1,v2,l));
  78.     }
  79.     if(edges.size() > 0)
  80.     {
  81.       sort(edges.begin(),edges.end(),cmpE);
  82.       //
  83.       AddToG(edges[edges.size()-1]);
  84.       //
  85.       for(int n = 1; n <= N; n++) // pro kazdy uzel
  86.       {
  87.         if(connected[n]) continue;
  88.         // najdu prvni hranu s timto uzlem k pripojenymu uzlu
  89.         int ei = FindEdge(n);
  90.         if(ei < 0)
  91.         {
  92.           disconnected = true;
  93.           break;
  94.         }
  95.         AddToG(edges[ei]);
  96.       }
  97.     }
  98.     else
  99.       disconnected = true;
  100.     //
  101.     if(disconnected)
  102.       cout << "disconnected\n";
  103.     else
  104.       cout << (total_length - (2*edges[edges.size()-1].l)) << '\n';
  105.   }
  106.   return 0;
  107. }

Diff to submission s1225

spider.cpp

--- c4.s1225.cteam054.spider.cpp.0.spider.cpp
+++ c4.s1268.cteam054.spider.cpp.0.spider.cpp
@@ -77,20 +77,25 @@
       edges.push_back(Edge(v1,v2,l));
     }
-    sort(edges.begin(),edges.end(),cmpE);
-    //
-    AddToG(edges[edges.size()-1]);
-    //
-    for(int n = 1; n <= N; n++) // pro kazdy uzel
+    if(edges.size() > 0)
     {
-      if(connected[n]) continue;
-      // najdu prvni hranu s timto uzlem k pripojenymu uzlu
-      int ei = FindEdge(n);
-      if(ei < 0)
+      sort(edges.begin(),edges.end(),cmpE);
+      //
+      AddToG(edges[edges.size()-1]);
+      //
+      for(int n = 1; n <= N; n++) // pro kazdy uzel
       {
-        disconnected = true;
-        break;
+        if(connected[n]) continue;
+        // najdu prvni hranu s timto uzlem k pripojenymu uzlu
+        int ei = FindEdge(n);
+        if(ei < 0)
+        {
+          disconnected = true;
+          break;
+        }
+        AddToG(edges[ei]);
       }
-      AddToG(edges[ei]);
     }
+    else
+      disconnected = true;
     //
     if(disconnected)