TIOJ 1212 圖論 之 最小圈測試

poao899    1124K    8531MS    G++     0.94K     2009-11-17 08:50:50                                     .


應該有很多方法可以加速不過先算了xD


Floyd-Warshall掃過去O(n^3)就過了囧


//***************************

#include<stdio.h>
#define INF 50000
#define MV 501
#define ME 250100
int getint(){
	int g=0,c=getchar();
	while(c=='\n'||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-48;
		c=getchar();
	}
	return g;
}
int n,m,dis[MV][MV],min;
struct edge{
	int j;
	edge *next;
}E[ME],*V[MV];
void set(edge *p){
	int i=getint();
	p->j=getint();
	edge *q=V[i];
	V[i]=p;
	p->next=q;
	dis[i][p->j]=1;
}
main(){
	while(1){
		n=getint();
		m=getint();
		if(!n&&!m)break;
		//Initialize
		min=INF;
		for(int i=0;i<MV;i++)
			for(int j=0;j<MV;j++)
				dis[i][j]=INF;
		//Construct
		for(int i=0;i<m;i++)
			set(E+i);
		//Floyd Warshall
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(dis[i][k]+dis[k][j]<dis[i][j])
						dis[i][j]=dis[i][k]+dis[k][j];
		//Cycle
		for(int i=1;i<=n;i++)
			if(dis[i][i]<min)
				min=dis[i][i];
		if(min!=INF)printf("%d\n",min);
		else puts("0");
	}
}