All Tracks Algorithms Graphs Minimum Spanning Tree Problem

Simulate Network

Algorithms, Easy-Medium, Graph Theory, Sorting


Globsoft has a network of $$N$$ computers connected by $$M$$ lan cables. It is possible to communicate between any two computers in the network using these cables. There can be multiple cables connecting $$2$$ computers. A computer may be connected via a cable to itself.

We say that computer $$A$$ can communicate with computer $$B$$, if there exists a sequence of cables connecting these $$2$$ computers directly or undirectly.

Each cable has a latency associated with it. Now, the company has decided to revamp the existing network and replace some existing cables with newer cables. You are given $$Q$$ new cables, each having its own latency. You can pick any number of cables (maybe $$0$$) from these $$Q$$ cables and use it to replace any cable in the existing network. Each new Cable can be used at most once. It is not necessary to replace every cable from the existing network.

Now, considering you use an arbitrary number of new cables and embed them into the existing network, you need to pick $$N-1$$ cables from this network (Can consist of old as well as new ) such that using these $$N-1$$ cables, it is posible to communicate beween any $$2$$ computers present in the network. What can be the minimum sum of latencies of these $$N-1$$ cables satisfying the above constraints, considering you perform the replacement of the cables optimally ?

Input Format:

The First line consists of two integers $$N$$ and $$M$$, $$N$$ is the number of computers in the network and $$M$$ is the number of cables in the network.
Next $$M$$ lines consists of three integers each: $$A$$, $$B$$ anc $$L$$, denoting there is a cable connecting computers $$A$$ and $$B$$ and having latency $$L$$.
Next line consists of an integer $$Q$$ denoting the number of cables available for use.
Next line consists of an array $$C$$ denoting the latencies of the $$Q$$ cables.

Output Format:

Output the required answer on a single line


$$1 \le N \le 10^5$$

$$1 \le M \le 10^5$$

$$1 \le A,B \le N$$

$$1\le L \le 10^6$$

$$0 \le Q \le 10^5$$

$$1 \le C[i] \le 10^6; 1 \le i \le Q$$

4 6
1 2 1
1 3 5
1 4 5
1 2 3
2 1 4
2 3 6
5 8 2 2 3

The computers 1 and 2 are connected by cables of latencies 1,3 and 4.
The computers 1 and 3 are connected by cable of latency 5.
The computers 1 and 4 are connected by cable of latency 5.
The computers 2 and 3 are connected by cable of latency 6.
The available cables have latencies: 5,8,2,2,3

If we take the cable of latency 1 between computers 1 and 2 (as given in the network), cable of latency 2 between computers 1 and 3 (from Q cables), cable of latency 2 between computers 1 and 4 (from Q cables), the latency of the network would be 1+2+2=5 , which is the minimum possible latency for the network.

Time Limit: 1.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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Globalsoft Backend Hiring Challenge

View All Notifications