SPFA整体过程

1.用一个队列`queue`支撑。

2.`dis[i]`表示目前`x`到`i`的距离。

3.`b[i]`表示`i`是否在`q`中。

4.清空队列`while(q.size()) q.pop();`。

5.初始化（把所有的`dis[i]`设为`INF`,再把`dis[x]`设为`0`，因为`x`到`x`的距离是`0`）。

6.把当先点入队`q.push(x);`。

7.取出队首，存在`temp`中,`b[队首]` = `false`。

8.更新每一个点(`dis[j] = min(dis[temp] + mp[temp][j],dis[j]);`)。

9.如果它没有在`q`中则把它入队，并把`b[i]`标记成`true`。

10.如果队列不空则继续第7步。

code

#include <iostream>

#include <queue>

using namespace std;

#define inf 0x3f3f3f3f

int mp[105][105], dis[105], vis[105], num[105], n, m;

queue<int> q;

void SPFA(int x) {

	while(q.size()) q.pop();//4

	for (int i = 1; i <= n; i++) {//5

		dis[i] = inf;

	}

	dis[x] = 0;

	q.push(x);//6

	while (!q.empty()) {

		int temp = q.front();//7

		q.pop();

		for (int j = 1; j <= n; j++) {//8

			if (dis[j] > mp[temp][j] + dis[temp]) {

				dis[j] = dis[temp] + mp[temp][j];

				if (!vis[j]) {//9

					q.push(j);

					vis[j] = 1;

					num[j]++;

				}

			}

		}

		vis[temp] = 0;

	}//10

}

int main() {

	while (cin >> n >> m && n + m) {

		int a, b, c;

		for (int i = 1; i <= n; i++) {/赋予INF

			for (int j = 1; j <= n; j++) {

				if (i == j) {、、特判

					mp[i][j] = 0;

				} else {

					mp[i][j] = inf;

				}

			}

		}

		for (int i = 1; i <= m; i++) {

			cin >> a >> b >> c;

			if (mp[a][b] > c) {

				//无向图

				mp[a][b] = mp[b][a] = c;

				//有向图

				//mp[a][b] = c;

			}

		}

		SPFA(1);

		cout << dis[n] << endl;

	}

	return 0;

}

完结散花！

巴特西

hdu-2544 最短路（SPFA）

SPFA整体过程

1.用一个队列`queue`支撑。

2.`dis[i]`表示目前`x`到`i`的距离。

3.`b[i]`表示`i`是否在`q`中。

4.清空队列`while(q.size()) q.pop();`。

5.初始化（把所有的`dis[i]`设为`INF`,再把`dis[x]`设为`0`，因为`x`到`x`的距离是`0`）。

6.把当先点入队`q.push(x);`。

7.取出队首，存在`temp`中,`b[队首]` = `false`。

8.更新每一个点(`dis[j] = min(dis[temp] + mp[temp][j],dis[j]);`)。

9.如果它没有在`q`中则把它入队，并把`b[i]`标记成`true`。

10.如果队列不空则继续第7步。

code

完结散花！

最新文章

热门文章

巴特西

hdu-2544 最短路（SPFA）

SPFA整体过程

1.用一个队列queue支撑。

2.dis[i]表示目前x到i的距离。

3.b[i]表示i是否在q中。

4.清空队列while(q.size()) q.pop();。

5.初始化（把所有的dis[i]设为INF,再把dis[x]设为0，因为x到x的距离是0）。

6.把当先点入队q.push(x);。

7.取出队首，存在temp中,b[队首] = false。

8.更新每一个点(dis[j] = min(dis[temp] + mp[temp][j],dis[j]);)。

9.如果它没有在q中则把它入队，并把b[i]标记成true。

10.如果队列不空则继续第7步。

code

完结散花！

最新文章

热门文章

1.用一个队列`queue`支撑。

2.`dis[i]`表示目前`x`到`i`的距离。

3.`b[i]`表示`i`是否在`q`中。

4.清空队列`while(q.size()) q.pop();`。

5.初始化（把所有的`dis[i]`设为`INF`,再把`dis[x]`设为`0`，因为`x`到`x`的距离是`0`）。

6.把当先点入队`q.push(x);`。

7.取出队首，存在`temp`中,`b[队首]` = `false`。

8.更新每一个点(`dis[j] = min(dis[temp] + mp[temp][j],dis[j]);`)。

9.如果它没有在`q`中则把它入队，并把`b[i]`标记成`true`。