All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Buying items
Tag(s):

Ad-Hoc, Algorithms, Brute-force search, Dijkstra's algorithm, Graph, Medium, Shortest path problem, 簡単-普通

Problem
Editorial
Analytics

There are n different types of objects. You want to buy atleast one instance of each type of object. There are m people , each of them sells one set of objects at a certain price (price is for the set).
Each of these m people sells either nothing or all the objects in the set he has. Information of these m sellers is represented by matrix M of size \(m * n \) . if \(M_{i,j} = 1\), it means that \(i^{th}\) seller has one \(j^{th}\) type of object in his set, otherwise \(M_{i,j} = 0\) . The \(i^{th}\) seller will sell set of all his objects at price \(C_i\).
You want to buy at least one object of each type (it is guaranteed that it is always possible to do so). Find the minimal cost needed to pay to achieve it.

\(\textbf{Input}\)

The first line contains two integers \(n, \; m\) separated by space. (\(1 \le n \times m \le 500\)).

The \((i + 1)^{th}\) (\(1 \le i \le m\)) line contains \((n + 1)\) integers - \(M_{i,1}, \; M_{i,2}, \; M_{i,3}, \dots, M_{i,n}, \; C_i\). (\(0 \le M_{i,j} \le 1, 1 \le C_i \le 10^9\)).

\(\textbf{Output}\)

Output the minimal cost you should pay to buy at least one object of each type.

SAMPLE INPUT
3 3
0 1 1 2
1 0 0 3
1 1 1 9
SAMPLE OUTPUT
5
Explanation

Buy from the 1 and 2 seller with cost \(2 + 3 = 5\).

Time Limit: 3.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: Bash, 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, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?