All Tracks Algorithms Graphs Minimum Spanning Tree Problem

Travelling Tom
Tag(s):

Algorithms, Bitmask, Graph Theory, Medium

Problem
Editorial
Analytics

Tom is visiting the country Hackerland. Hackerland has $$n$$ cities and $$m$$ bi-directional roads. There are $$k$$ types of tokens. Token $$i$$ costs $$c_i $$. The costs of the tokens are such that for all $$2 \le i \le k$$, $$ c_i \ge 2 c_{i - 1} $$. For each road, you need to have a particular set of tokens, if you want to travel it. Note that you don't have to give the tokens, you just need to show them. Thus, one token can be used at any number of roads, where it is required. Tom wants to select a set of tokens, such that using them, he can go from any city to any other city. You have to help him minimize the total cost of tokens he buys.

Input:

  • The first line contains three space separated integers, $$n, $$ $$m$$ and $$k$$ .
  • The second line contains $$k$$ space separated integers, where the $$i^{\text{th}} $$ integer denotes the price of $$i^{\text{th}} $$ token, i.e. $$c_i$$ .
  • $$i^{\text{th}} $$ of the next $$m$$ lines contains three integers $$u_i, v_i, l_i$$, where $$l_i$$ is the number of tokens required by the $$i^{\text{th}} $$ road, followed by $$l_i$$ indices denoting the tokens required. This road connects cities $$u_i$$ and $$v_i$$

Output:

  • Print one integer containing the minimum cost of tokens Tom has to buy, such that he can travel from any city to any other city. If it is impossible to choose such a set of tokens, print $$-1$$.

Constraints

  • $$1 \le n \le 10^5 $$

  • $$ 1 \le m \le 10^5 $$

  • No road connects a city to the same city. However, there can be multiple roads between two cities.

  • $$ 1 \le c_i \le 10^{18} $$

  • For all $$2 \le i \le k $$, $$c_i \ge 2 c_{i - 1} $$

SAMPLE INPUT
3 3 4
1 2 5 10
1 2 2 1 2
1 3 1 3
2 3 1 4
SAMPLE OUTPUT
8
Explanation

The best way for tom is to buy the first three tokens. Using these tokens, he can use the roads $$1$$ and $$2$$, and using the roads he can go from any city to any other city. The minimum cost is therefore $$8$$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications