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次松弛就可以松弛到了所有的边（不一定是最短路）。这样一来，我们设置的步数限制意义就不太明显。我们要的是，从原点开始，首先松弛原点，之后松弛和原点相连的所有点，如此下去。一直到超过步数限制。要达到这一目的，我们松弛边的时候，最好是从远离原点的顶点开始松弛（最好是从终点开始），这样一来，就可以保证第一次松弛的是原点相连的边，第二次松弛是松弛与原点相连的顶点，如此类推。
后记：
1.有步数限制的最短路，按照kelefe大牛的说法，还可以通过拆点后用dijkstra算法实现。但是个人到现在还没有想明白为什么……
2.从这个题目看来，个人对算法的理解和熟悉程度还是不够。钻研得不够。因为无论是bellman ford还是dijkstra算法，都是学过的，但是却不会迁移，这说明了以后学习算法的时候，要研究深一点。
＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝
using namespace std;
#define Max 1000000
int d[1001], n, m, t, g[1001][1001], l;
void bellman_ford()
{
int i, j, k;
for (i = 0; i < l; i++)
for (j = n - 1; j >= 0; j--)
for (k = n - 1; k >= 0; k--)
if (g[j][k] && d[k] > d[j] + g[j][k])
d[k] = d[j] + g[j][k];
}
int main()
{
int a, b, i;
while (cin >> n >> m >> t, n)
{
memset(g, 0, sizeof(g));
l = n > 10 ? 10 : n;
for (i = 0; i < n; i++) d[i] = Max;
d[0] = 0;
for (i = 0; i < m; i++)
{
cin >> a >> b;
if (a == b) cin >> a;
else
{
cin >> g[a][b];
g[b][a] = g[a][b];
}
}
bellman_ford();
if (d[t] < Max) cout << d[t] << endl;
else cout << "no\n";
}
return 0;
}
评论 (0)