Sicily Shortest path in unweighted graph

本文主要是介绍Sicily Shortest path in unweighted graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Source:

http://soj.sysu.edu.cn/show_problem.php?pid=1003&cid=2104

Description

输入一个无向图，指定一个顶点s开始bfs遍历，求出s到图中每个点的最短距离。
如果不存在s到t的路径，则记s到t的距离为-1。

Sample Input

输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。
以下m行，每行是一个数对v y，表示存在边(v,y)。顶点编号从1开始。

5 3
1 2
1 3
2 4

Sample Output

记s=1，在一行中依次输出：顶点1到s的最短距离，顶点2到s的最短距离，…，顶点n到s的最短距离。
每项输出之后加一个空格，包括最后一项。

0 1 1 2 -1 

Caution:

这道题其实就是最短路问题的弱化版，bfs之。
但是，在这发现了memset和fill的区别：

memset是对每个字节赋值，而fill是区域赋值，所以memset有时候会出现谬误。

例：memset(a,1,sizeof(a))
memset将a中的每个元素都按字节赋值为2进制数“1”：
00000001000000010000000100000001
而转回10进制就变成了16843009
这与预期的完全不一致！

所以，memset对char数组无限制，对int数组只能赋0或-1； 而fill均可

示例代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include <vector>using namespace std;int n, m, v, y;
int oo = 1 << 30;
vector<int> g[10001];
int d[10001];void init()
{fill(d, d + 10001, oo);//memset(d, oo, sizeof(d));cin >> n >> m;while (m--){cin >> v >> y;g[v].push_back(y);g[y].push_back(v);}
}void bfs(int s)
{d[s] = 0;queue<int> q;q.push(s);while (!q.empty()){int u = q.front();for (int i = 0; i < g[u].size(); ++i){if (d[g[u][i]] > d[u] + 1){d[g[u][i]] = d[u] + 1;q.push(g[u][i]);}}q.pop();}
}void solve()
{bfs(1);for (int i = 1; i <= n; ++i){if (d[i] != oo)cout << d[i] << " ";elsecout << -1 << " ";}
}int main()
{init();solve();return 0;
}

这篇关于Sicily Shortest path in unweighted graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---