- #include
- #defineMAXN 1000+1#defineMAXM 500000+1#definePair pair
- using namespace std;
- int n,m,t,v[MAXN],num;
- int head[MAXN],g[MAXN][MAXN];
- queue emp;
- struct Edge{
- int dis;
- int to,next;
- }edge[MAXM];
- int read()
- {
- int in=0;
- charch=getchar();
- for(;ch>'9'||ch<'0';ch=getchar());
- for(;ch>='0'&&ch<='9';ch=getchar())in=in*10+ch-'0';
- return in;
- }
- voidadd(int from,intto,int dis)
- {
- edge[++num].next=head[from];
- edge[num].to=to;
- edge[num].dis=dis;
- head[from]=num;
- }
- voidbfs(ints,int&maxl)
- {
- memset(v,0,sizeof(v));
- queue h=emp;
- h.push(Pair(0,s));
- while(h.size()>0)
- {
- intk=h.front().second,diss=h.front().first;h.pop();v[k]=1;
- for(inti=head[k];i;i=edge[i].next)
- if(v[edge[i].to]==0)
- {
- v[edge[i].to]=1;
- g[edge[i].to][k]=g[k][edge[i].to]=diss+1;
- h.push(Pair(diss+1,edge[i].to));
- maxl=max(maxl,diss+1);
- }
- }
- }
- voiddij(int s)
- {
- memset(v,0,sizeof(v));
- priority_queue,greater > h;
- intdis[MAXN],maxx=0;for(inti=1;i<=n;i++) dis[i]=999999999;
- dis[s]=0;
- h.push(Pair(dis[s],s));
- while(h.size()>0)
- {
- intk=h.top().second;h.pop();
- if(v[k])continue;
- v[k]=1;
- for(inti=head[k];i;i=edge[i].next)
- {
- if(dis[k]+edge[i].dis<dis[edge[i].to])
- {
- dis[edge[i].to]=dis[k]+edge[i].dis;
- h.push(Pair(dis[edge[i].to],edge[i].to));
- }
- }
- }
- queue<int> q;
- for(inti=1;i<=n;i++)
- if(dis[i]!=999999999) maxx=max(maxx,dis[i]);
- for(inti=1;i<=n;i++)if(dis[i]==maxx) q.push(i);
- if(maxx!=0)
- while(q.size()>0)
- {
- bfs(q.front(),maxx);q.pop();
- }
- else
- {
- for(inti=1;i<=n;i++)
- {
- bfs(i,maxx);
- }
- }
- printf("%d\n",maxx*100);
- }
- int main()
- {
- while(scanf("%d%d",&n,&m)==2)
- {
- intmaxl=0;
- if(m==0&&n==0)return 0;
- memset(edge,0,sizeof(edge));
- memset(g,0,sizeof(g));
- num=0;//memset(dis,0,sizeof(dis));memset(head,0,sizeof(head));
- for(inti=1;i<=m;i++)
- {
- inta,b;a=read();b=read();
- add(a,b,1);
- add(b,a,1);
- }
- dij(1);
- }
- return 0;
- }
来源: