codeforces-scrape

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

17B.md (2098B)


      1 Source: https://codeforces.com/problemset/problem/17/B
      2 
      3 B. Hierarchy
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 64 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Nick's company employed *n* people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are *m* applications written in the following form: «employee *a**i* is ready to become a supervisor of employee *b**i* at extra cost *c**i*». The qualification *q**j* of each employee is known, and for each application the following is true: *q**a**i* > *q**b**i*.
     22 
     23 Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.
     24 
     25 Input
     26 
     27 The first input line contains integer *n* (1 ≤ *n* ≤ 1000) — amount of employees in the company. The following line contains *n* space-separated numbers *q**j* (0 ≤ *q**j* ≤ 106)— the employees' qualifications. The following line contains number *m* (0 ≤ *m* ≤ 10000) — amount of received applications. The following *m* lines contain the applications themselves, each of them in the form of three space-separated numbers: *a**i*, *b**i* and *c**i* (1 ≤ *a**i*, *b**i* ≤ *n*, 0 ≤ *c**i* ≤ 106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application *q**a**i* > *q**b**i*.
     28 
     29 Output
     30 
     31 Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 4  
     39 7 2 3 1  
     40 4  
     41 1 2 5  
     42 2 4 1  
     43 3 4 1  
     44 1 3 5
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 11
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 3  
     57 1 2 3  
     58 2  
     59 3 1 2  
     60 3 1 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 -1
     67 ```
     68 
     69 Note
     70 
     71 In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -1.