Source code for submission s739

Go to diff to previous submission

fr.cpp

  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int last )
  7. {	
  8. 	int prize = values[ pair<int, int>( X, last ) ];
  9.  
  10. 	multimap<int, int>::iterator from = edges.lower_bound( X );
  11. 	multimap<int, int>::iterator to = edges.upper_bound( X );
  12.  
  13. 	int sum = 0; int x = 0;
  14. 	for ( ; from != to; ++from ) {
  15. 		if ( from->second != last ) {
  16. 			x++;
  17. 			sum += getCountFor( edges, values, from->second, X );
  18. 		}
  19. 	}
  20.  
  21. 	if ( X == last ) {
  22. 		return sum;
  23. 	}
  24.  
  25. 	if (x == 0) {
  26. 		return prize;
  27. 	}
  28.  
  29. 	return prize > sum ? sum : prize;
  30. }
  31.  
  32. int main ( void )
  33. {
  34. 	int N, C;
  35.  
  36. 	while ( cin >> N >> C ) {
  37. 		multimap<int, int> edges;
  38. 		map<pair<int, int>, int> values;
  39.  
  40. 		values[pair<int, int>(C, C)] = 1000000000;
  41.  
  42. 		int U, V, W;
  43. 		for ( int i = 0; i < N - 1; i++ ) {
  44. 			cin >> U >> V >> W;
  45.  
  46. 			pair<int, int> p1( U, V );
  47. 			pair<int, int> p2( V, U );
  48.  
  49. 			edges.insert(p1);
  50. 			edges.insert(p2);
  51.  
  52. 			values[ p1 ] = W;
  53. 			values[ p2 ] = W;
  54. 		}
  55.  
  56. 		cout << getCountFor(edges, values, C, C) << endl;
  57. 	}
  58.  
  59. 	return 0;
  60. }
  61.  
  62.  

Diff to submission s728

fr.cpp

--- c5.s728.cteam021.fr.cpp.0.fr.cpp
+++ c5.s739.cteam021.fr.cpp.0.fr.cpp
@@ -19,4 +19,8 @@
         }
         
+        if ( X == last ) {
+                return sum;
+        }
+        
         if (x == 0) {
                 return prize;
@@ -34,5 +38,5 @@
                 map<pair<int, int>, int> values;
                 
-                values[pair<int, int>(C, C)] = 10000;
+                values[pair<int, int>(C, C)] = 1000000000;
 
                 int U, V, W;