Source code for submission s1225

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.     sort(edges.begin(),edges.end(),cmpE);
  80.     //
  81.     AddToG(edges[edges.size()-1]);
  82.     //
  83.     for(int n = 1; n <= N; n++) // pro kazdy uzel
  84.     {
  85.       if(connected[n]) continue;
  86.       // najdu prvni hranu s timto uzlem k pripojenymu uzlu
  87.       int ei = FindEdge(n);
  88.       if(ei < 0)
  89.       {
  90.         disconnected = true;
  91.         break;
  92.       }
  93.       AddToG(edges[ei]);
  94.     }
  95.     //
  96.     if(disconnected)
  97.       cout << "disconnected\n";
  98.     else
  99.       cout << (total_length - (2*edges[edges.size()-1].l)) << '\n';
  100.   }
  101.   return 0;
  102. }

Diff to submission s1184

spider.cpp

--- c4.s1184.cteam054.spider.cpp.0.spider.cpp
+++ c4.s1225.cteam054.spider.cpp.0.spider.cpp
@@ -24,5 +24,4 @@
 
 vector<Edge> edges;
-vector<Edge> tree;
 
 void print_edges(const vector<Edge> &edges)
@@ -35,5 +34,4 @@
 void AddToG(const Edge &e)
 {
-  tree.push_back(e);
   total_length += e.l;
   connected[e.v1] = true;
@@ -69,5 +67,4 @@
     if(cin.eof()) break;
     //
-    tree.clear();
     edges.clear();
     memset(connected,0,2001);
@@ -95,5 +92,4 @@
       }
       AddToG(edges[ei]);
-      edges.erase(edges.begin()+ei);
     }
     //