顺便说一下这题
我的思路是最短路算法的变种，可以运用最短路的思想在扩展节点（松弛操作）的时候改变可行条件
原：dis[j]>dis[i]+g[i][j]
改：dis[j]<min(dis[i],g[i][j])
初始dis[1]=oo
除了floyd应该都行吧。