All Tracks Algorithms Graphs Minimum Cost Maximum Flow Problem

Salesmen problem
Tag(s):

Algorithms, Hungarian, Medium

Problem
Editorial
Analytics

You are working in a salesmen company as a programmer.

There are $$n$$ towns in your country and $$m$$ directed roads between them. Each road has a cost person should spend on fuel. The company wants to sell goods in all $$n$$ towns. There are infinitely many salesmen in the company. We can choose some positive number of salesmen and give a non-empty list of towns to each of them. Towns from the list are the towns to sell goods in. Each salesman will visit all the towns in his list in this particular order in cycle (after the last town he will return to the first town and so on). Salesman can visit other towns on his way but he will not sell goods in these towns. Two salesmen cannot sell goods in one town because it will attract unnecessary attention to your company. But for every town there must be a salesman who sell goods in this town. If salesman's list of towns consists of exactly one town then he should pay fee to stay in this town each month (each town has its own fee) or he should go for a round trip and spend money on fuel.

Your task is to calculate the minimal amount of money company must spend monthly to achieve its goals. We will assume that every salesman will spend a month to make one cycle.

Input format

The first line of input contains two integers $$n$$ and $$m$$ - number of towns and number of directed roads between them respectively ($$1 \le n \le 500$$, $$0 \le m \le n(n-1)$$).

The second line contains $$n$$ numbers $$a_{i}$$ - monthly fee for $$i$$-th town ($$0 \le a_i \le 10^{9}$$).

Next $$m$$ lines describe roads. Each description looks like $$u$$ $$v$$ $$cost$$ and describes a road from town $$u$$ to town $$v$$ with assigned cost $$cost$$ ($$1 \le u,v \le n$$, $$u \ne v$$, $$0 \le cost \le 10^{9}$$). It is guaranteed that there are no two roads between the same pair of towns in the same direction.

Output format

Print one integer - the minimal amount of money to spend.

Scoring

$$n \le 5$$ - 5 points

$$n \le 16$$ - 25 points

$$n \le 80$$ - 30 points

$$n \le 500$$ - 40 points

SAMPLE INPUT
3 3
30 25 30
1 2 3
2 3 5
3 1 10
SAMPLE OUTPUT
18
Explanation

In given test one has to choose one salesman and make him sell his goods in cities $$1 \rightarrow 2 \rightarrow 3$$ during one month.

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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications