codeforces-scrape

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

802J1.md (2529B)


      1 Source: https://codeforces.com/problemset/problem/802/J1
      2 
      3 J1. Send the Fool Further! (easy)
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on.
     22 
     23 Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank?
     24 
     25 Heidi's *n* friends are labeled 0 through *n* - 1, and their network of connections forms a tree. In other words, every two of her friends *a*, *b* know each other, possibly indirectly (there is a sequence of friends starting from *a* and ending on *b* and such that each two consecutive friends in the sequence know each other directly), and there are exactly *n* - 1 pairs of friends who know each other directly.
     26 
     27 Jenny is given the number 0.
     28 
     29 Input
     30 
     31 The first line of the input contains the number of friends *n* (3 ≤ *n* ≤ 100). The next *n* - 1 lines each contain three space-separated integers *u*, *v* and *c* (0 ≤ *u*, *v* ≤ *n* - 1, 1 ≤ *c* ≤ 104), meaning that *u* and *v* are friends (know each other directly) and the cost for travelling between *u* and *v* is *c*.
     32 
     33 It is guaranteed that the social network of the input forms a tree.
     34 
     35 Output
     36 
     37 Output a single integer – the maximum sum of costs.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 4  
     45 0 1 4  
     46 0 2 2  
     47 2 3 3
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 5
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 6  
     60 1 2 3  
     61 0 2 100  
     62 1 4 2  
     63 0 3 7  
     64 3 5 10
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 105
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 11  
     77 1 0 1664  
     78 2 0 881  
     79 3 2 4670  
     80 4 2 1555  
     81 5 1 1870  
     82 6 2 1265  
     83 7 2 288  
     84 8 7 2266  
     85 9 2 1536  
     86 10 6 3378
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 5551
     93 ```
     94 
     95 Note
     96 
     97 In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).