  Let us consider a parametric weighted directed graph in which every arc
$(j,i)$ has weight of the form
$w((j,i))=\max(P_{ij}+\lambda,I_{ij}-\lambda,C_{ij})$, where $\lambda$ is a
real parameter and $P$, $I$ and $C$ are arbitrary square matrices with elements
in $\mathbb{R}\cup\{-\infty\}$. In this paper, we design an algorithm that
solves the Non-positive Circuit weight Problem (NCP) on this class of
parametric graphs, which consists in finding all values of $\lambda$ such that
the graph does not contain circuits with positive weight. This problem, which
generalizes other instances of the NCP previously investigated in the
literature, has applications in the consistency analysis of a class of
discrete-event systems called P-time event graphs. The proposed algorithm is
based on max-plus algebra and formal languages, and improves the worst-case
complexity of other existing approaches, achieving strongly polynomial time
complexity $\mathcal{O}(n^4)$ (where $n$ is the number of nodes in the graph).
