锰锌袜子求最短路最快时间复杂度

给你一个 $n\times m$ 的网格，对于每个整点 $\text{(i,\ j)}$ 能连向给定一个圆环（每个点圆环内径外径不完全相同）范围内任意的整点，边权为 $a_{i,j}$，给你 $q$ 个点，求一个点 $\text{(i,\ j)}$ 到 $q$ 个点的最短路之和+$b_{i,j}$ 的最小值。

$q\le10$, $n,m\le150$, $\max(n,m)q\le500$, $0\le a_{i,j},b_{i,j}\le 10000$，求最快能做到的时间复杂度。