$(max,+)$ matrix product with limited number of values

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$, for some $n\times n$ matrices $A$ and $B$. This lower bound means that the trivial algorithm is the best one.

Is there a better algorithm if we restrict the values to be in a finite set? For example, all the matrix entries are $0$ or $1$. Note that this is different from Boolean matrix product.

Any reference is welcome.

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max_{A} \sum_{a\in A} a = -\min_{A} -\sum_{a\in A}a = -\min_A \sum_{a\in A}-a$, we can express a $(\max,+)$-matrix product as a $(\min,+)$-matrix product and vice versa, as the paper allows edge-weights to be either positive or negative.

So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.

StackExchange Computer Science Q#70463, answer score: 4