sicily1700 Ping
题目大意就是：有一些点，点与点之间有权值，现在有一个信息，要从源送到终点，问最少时间。如果信息到达A，则下一步，信息会发送给A相连的所有点。假设B和A相连，那么下一步，就会从B发送给所有与B相连的点，包括A。这样一来就会出现一些死循环，所以就有步数限制（10）。问题其实就是一个单源最短路径的问题，但是加上了步数限制。这个问题经过kelefe大牛的指点，终于做出来了～就是把bellman ford算法进行变形。bellman ford算法一共对n-1条边进行松弛而达到求全图最短路径的目的（因为一个有n个点的图，其最短路径的边数一定不会超过n-1）。按照这个思想，我们只要对图进行k次松弛（k是步数限制），就可以求出步数不超过k的最短路，这是主要思想。但是单单有这个思想还是不够的。因为bellman ford算法对边松弛的顺序会导致每次松弛的结果不同。比如说，如果从源开始松弛，则1次松弛就可以松弛到了所有的边（不一定是最短路）。这样一来，我们设置的步数限制意义就不太明显。我们要的是，从原点开始，首先松弛原点，之后松弛和原点相连的所有点，如此下去。一直到超过步数限制。要达到这一目的，我们松弛边的时候，最好是从远离原点的顶点开始松弛（最好是从终点开始），这样一来，就可以保证第一次松弛的是原点相连的边，第二次松弛是松弛与原点相连的顶点，如此类推。