Let p and t, p ≥ t, be positive integers. A t-composition of p is an ordered t-tuple of positive integers summing p. If T = (s1, s2, . . . , st) is a t-composition p and W is a p − (t − 1) × t matrix, then \( W(T) = \sum\limits_{k = 1}^t {{w_{{s_k}k}}} \) is called the weight of the t-composition T. We show that finding a minimum weight t-composition of p can be reduced to the determination of the shortest path in a certain digraph with O(tp) vertices. This study was motivated by a problem arising from the automobile industry, and the presented result is useful when dealing with huge location problems.