六度分离

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4213    Accepted Submission(s): 1718

8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0

Yes
Yes

题意：求n个节点中是否有两个节点间的最短距离大于7，若是则No，否则Yes。

题解：直接套Floyd的模板，然后再用两个for循环判断各点间的最短路径。

#include <stdio.h>
#include <string.h>
#define INF -1
#define maxn 102

int map[maxn][maxn], ok;

void Floyd(int n)
{
	int i, j, k;
	for(k = 0; k < n; ++k)
		for(i = 0; i < n; ++i)
			for(j = 0; j < n; ++j)
				if(map[i][k] != INF && map[k][j] != INF && (map[i][k] + map[k][j] < map[i][j] || map[i][j] == INF))
					map[i][j] = map[i][k] + map[k][j];
	
}

int main()
{
	int n, m, i, j, a, b;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(map, -1, sizeof(map));
		for(i = 0; i < n; ++i) map[i][i] = 0;
		for(i = 0; i < m; ++i){
			scanf("%d%d", &a, &b);
			map[a][b] = map[b][a] = 1;
		}
		Floyd(n);
		for(i = 0, ok = 1; i < n && ok; ++i)
			for(j = 0; j < n; ++j)
				if(map[i][j] == INF || map[i][j] > 7){
					ok = 0; break;
				}
		printf(ok ? "Yes\n" : "No\n");
	}
	return 0;
}

HDU1869 六度分离 【Floyd】,布布扣,bubuko.com

HDU1869 六度分离 【Floyd】

原文：http://blog.csdn.net/chang_mu/article/details/38231011