CF131D的题解
注意到 \(n\) 实在是小到不行，我们可以直接采用比较暴力的做法。
（嗯，可能算比较暴力吧
很简单，找环，然后把环里的所有点全部压进 dijkstra 的优先队列就行了。
找环最坏 \(n\) 遍跑满的 dfs，最短路是 \(O(n\log n)\) 的，最坏时间复杂度为 \(O(n^2)\)，稳过。
什么？怎么找环？都2202年了不会还有人不会找环吧qwq
对每一个点为起始点，都跑一边 dfs，一边跑一边标记，如果跑的时候碰到已经标记好的点，就说明碰到环了（注意不是标记完环了，现在还不能退出来因为我们标记的点中有多余的点，并不是单纯的环）。如果没有碰到就取消标记。
什么时候结束 dfs 呢？就是如果我们找到一个点是我们的起始点就可以结束了，此时易知我们现在标记的所有点就是环。
最后就快乐地上最短路啦~
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct edge
{
int v;
int w;
int nxt;
}e[6010];
int head[3010],tot;
void add(int u,int v,int w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
int n;
bool flag[3010];
bool ry,qwq;
void dfs(int u,int fa,int st)
{
flag[u]=1;//标记
for(int i=head[u];i&&!qwq;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa) continue;
if(flag[v])//找到环了
{
if(v==st) ry=1;//现在标记的点是环，可以退出dfs了
qwq=1;
return ;
}
dfs(v,u,st);
}
if(!qwq) flag[u]=0;//从当前节点出发没有碰到环的话就取消标记
}
int dis[3010];
bool vis[3010];
void dij()//人尽皆知的东西
{
priority_queue<pair<int,int> > q;
memset(dis,0x7f,sizeof(dis));
for(int i=1;i<=n;i++)
if(flag[i])
{
dis[i]=0;
q.push(make_pair(0,i));
}
int u;
while(!q.empty())
{
u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1,u,v;i<=n;i++)
{
scanf("%d%d",&u,&v);
add(u,v,1),add(v,u,1);
}
for(int i=1;i<=n&&!ry;i++)//对每个点都跑一遍dfs
{
qwq=0;
memset(flag,0,sizeof(flag));//记得初始化
dfs(i,0,i);
}
dij();
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}