思路：这题的N有500，直接floyd肯定超时。
我的做法是每次枚举一个点，求出包含这个点的最小环。
对所有最小环取最小值。求包含某个点的最小环我用的是启发式搜索，先以该点求一次spfa，然后dfs解决问题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxn 600
#define inf 1000000
using namespace std;
int head[Maxn],vi[Maxn],dis[Maxn],e,que[Maxn*],ans,dist[Maxn];
struct Edge{
int u,v,next;
}edge[Maxn*];
void init()
{
memset(head,-,sizeof(head));
memset(vi,,sizeof(vi));
e=;
}
void add(int u,int v)
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
edge[e].u=v,edge[e].v=u,edge[e].next=head[v],head[v]=e++;
} void spfa(int u)
{
int i,j,v,now,rear,he;
for(i=;i<Maxn;i++){
dist[i]=inf;
vi[i]=;
}
dist[u]=;
he=rear=;
que[he++]=u;
while(he!=rear){
now=que[rear++];
vi[now]=;
for(i=head[now];i!=-;i=edge[i].next){
v=edge[i].v;
if(v==now) continue;
if(dist[now]+<dist[v]){
dist[v]=dist[now]+;
if(!vi[v]){
que[he++]=v;
vi[v]=;
}
}
}
}
return ;
}
void dfs(int u,int pre)
{
int i,v;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(v==pre) continue;
if(dis[v]==){
ans=min(ans,dis[u]+);
continue;
}
if(dis[u]+dist[u]>=ans)
return ;
if(dis[u]+<dis[v]){
dis[v]=dis[u]+;
dfs(v,u);
}
}
}
int main()
{
int n,m,i,j,u,v,t,Ca=;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&m);
for(i=;i<=m;i++){
scanf("%d%d",&u,&v);
u++,v++;
add(u,v);
}
ans=inf;
for(i=;i<=n;i++){
for(j=;j<=n;j++)
dis[j]=inf;
dis[i]=;
spfa(i);
dfs(i,);
}
printf("Case %d: ",++Ca);
if(ans>=inf)
printf("impossible\n");
else
printf("%d\n",ans);
}
return ;
}