学步园

这个题目,我一看到的居然是用DFS,汗了,,,但是我写着写着,还居然给过了样例,和自己的一些特殊数据,,但是到后来我突然就觉得不对了,,因为一出现环数据就过不了了,而我又不想在研究研究求出最小值,但是这个思路还是可行的...但是麻烦,我就不写出来了.

然后floyd算法还是比较简单的.只用个三重循环,然后再来个二重循环就可以整出来了,代码非常好实现,

代码如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int N,M;
int map[205][205];

void Floyd()
{
	for(int k=0;k<=N;k++)
		for(int i=0;i<=N;i++)
			for(int j=0;j<=N;j++)
			if(map[i][j]>map[i][k]+map[k][j]&&map[i][k]!=0x3f3f3f3f&&map[k][j]!=0x3f3f3f3f)
				map[i][j]=map[i][k]+map[k][j];

}
int judge()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			//printf("sta=%d end=%d, step=%d",i,j,map[i][j]);
			//printf("\n");
			if(map[i][j]>7)
			{
				return 0;
			}
		}
	}
	return 1;
}

int main()
{
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		int a,b;
		memset(map,0x3f,sizeof(map));
		for(int kk=0;kk<N;kk++)
			map[kk][kk]=0;
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d",&a,&b);
			map[a][b]=1;
			map[b][a]=1;
		}
		Floyd();
		if(judge())
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

当然我也想把我的DFS也贴出来 嘿嘿,虽然是错的,但毕竟是一种思路不,,呼呼

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int N,M;//N represents the number of points,and M stands for the number of edges;
int idx;
int head[105];
int step;
int flag;
int visit[105];
struct Edge
{
	int v;
	int next;
}e[205];

void addedge(int a,int b)
{
	idx++;
	e[idx].v=b;
	e[idx].next=head[a];
	head[a]=idx;
}

void DFS(int a,int step)
{
	if(step>6)
	{
		flag=0;
		return;
	}
	for(int p=head[a];p!=-1;p=e[p].next)
	{
		if(flag==1&&!visit[e[p].v])
		{
			visit[e[p].v]=1;
			DFS(e[p].v,step+1);
			visit[e[p].v]=0;
		}

	}
}

int main()
{
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		int a,b;
		int t=-1;
		idx=0;
		memset(head,-1,sizeof(head));
		for(int i=0;i<M;i++)
		{
			scanf("%d%d",&a,&b);
			addedge(a,b);
			addedge(b,a);
		}
		for(i=0;i<N;i++)
		{
			flag=1;
			memset(visit,0,sizeof(visit));
			visit[i]=1;
			DFS(i,-1);
			if(flag==0)
			{
				printf("No\n");
				break;
			}
			visit[i]=0;
		}
		if(t<=6&&flag==1)
			printf("Yes\n");
	}
	return 0;
}

#include <stdio.h>
#include  <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#define inf 0x3fffffff
#define inf2 0x3f3f3f3f


using namespace std;

int map[555][555];


int N,M;

void Floyd()
{
	for(int k=1; k <= N; k++)
	{
		for(int i=1; i <= N ; i++ )
		{
			for(int j=1 ;j <= N;j++)
			{
				if(map[i][j]>map[i][k]+map[k][j]&&map[i][k]!=inf2&&map[k][j]!=inf2)
				map[i][j]=map[i][k]+map[k][j];
			}
		}
	}
}



int main()
{
	while(scanf("%d %d" ,&N, &M)!=EOF)
	{
		int a, b;
		int min=inf;
		int val;
		memset(map,0x3f3f3f3f,sizeof(map));
		for(int i=1 ; i<=M ;i++ )
		{
			scanf("%d %d %d " , &a , &b ,&val );
			if(map[a][b]>val)
			{
				map[a][b]=val;
				map[b][a]=val;
			}
		}
		Floyd();
		while(cin >> a >> b)
		{
			cout << map[a][b] << endl;
		}		
	}
	return 0;
}