codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

24A.md (1865B)


      1 Source: https://codeforces.com/problemset/problem/24/A
      2 
      3 A. Ring road
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Nowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all *n* cities of Berland were connected by *n* two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all *n* roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?
     22 
     23 Input
     24 
     25 The first line contains integer *n* (3 ≤ *n* ≤ 100) — amount of cities (and roads) in Berland. Next *n* lines contain description of roads. Each road is described by three integers *a**i*, *b**i*, *c**i* (1 ≤ *a**i*, *b**i* ≤ *n*, *a**i* ≠ *b**i*, 1 ≤ *c**i* ≤ 100) — road is directed from city *a**i* to city *b**i*, redirecting the traffic costs *c**i*.
     26 
     27 Output
     28 
     29 Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.
     30 
     31 Examples
     32 
     33 Input
     34 
     35 ```
     36 3  
     37 1 3 1  
     38 1 2 1  
     39 3 2 1
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 1
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 3  
     52 1 3 1  
     53 1 2 5  
     54 3 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 6  
     67 1 5 4  
     68 5 3 8  
     69 2 4 15  
     70 1 6 16  
     71 2 3 23  
     72 4 6 42
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 39
     79 ```
     80 
     81 Input
     82 
     83 ```
     84 4  
     85 1 2 9  
     86 2 3 8  
     87 3 4 7  
     88 4 1 5
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 0
     95 ```