Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Snoopy and Reza are best friends and today is Reza's birthday. Now Snoopy wants to join Reza's birthday celebration and gift him some balloons. In their country, there are cities numbered from to . Snoopy lives in city and Reza lives in city . There are bidirectional roads, the road is between the city and and is the cost of using this road. There is a weird rule in their country. For every road , there is a restriction , which means one can use the road carrying at most balloons. Initially, Snoopy has taka and balloons.
Now Snoopy wants to know what is the maximum number of balloons he can gift Reza. For this he wants your help.
Print the maximum number of balloons Snoopy can gift.
Input | Output |
---|---|
5 4 9 15 1 2 3 10 1 4 10 12 2 5 4 12 4 5 9 15 | 10 |
Snoopy can choose the path 1->2->5 which costs 7 and he can gift 10 balloons. |
Input | Output |
---|---|
5 5 15 15 1 3 4 12 1 4 3 10 4 2 8 10 3 2 16 12 2 5 4 12 | 10 |
Snoppy can choose the path 1->4->2->5 which costs 15 and he can gift 10 balloons. |
Input | Output |
---|---|
6 6 20 7 1 2 1 20 2 3 1 20 3 4 1 30 3 5 1 10 4 6 1 3 5 6 2 5 | 5 |
Snoppy can choose the path 1->2->3->5->6 which costs 5 and he can gift 5 balloons. |
82% Solution Ratio
Fizzz_83Earliest,
Zihad_BdFastest, 0.0s
AUST_GriffinsLightest, 1.8 MB
Zobayer_AbedinShortest, 1096B
Login to submit