  Quantitative games are two-player zero-sum games played on directed weighted
graphs. Total-payoff games (that can be seen as a refinement of the
well-studied mean-payoff games) are the variant where the payoff of a play is
computed as the sum of the weights. Our aim is to describe the first
pseudo-polynomial time algorithm for total-payoff games in the presence of
arbitrary weights. It consists of a non-trivial application of the value
iteration paradigm. Indeed, it requires to study, as a milestone, a refinement
of these games, called min-cost reachability games, where we add a reachability
objective to one of the players. For these games, we give an efficient value
iteration algorithm to compute the values and optimal strategies (when they
exist), that runs in pseudo-polynomial time. We also propose heuristics
allowing one to possibly speed up the computations in both cases.

Computer Science and Game Theory