首页 > 代码库 > 2016弱校联盟十一专场10.2——Floyd-Warshall
2016弱校联盟十一专场10.2——Floyd-Warshall
题目链接：Floyd-Warshall
题意：
给你n个点，m条边，100>m-n>0，现在有q个询问，问你任意两点的最短距离，题目保证每条边都被连接，每条边的距离为1
题解：
首先我们可以看到边最多只比点多100个，那么我们可以先将n-1条边生成一棵树，然后用LCA来求最短距离。
然而有可能最短路在多余的这100条边上，所以我们将这100条边的两个端点到所有点的最短路用bfs预处理出来，
然后再用来更新一下答案就行。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define F(i,a,b) for(int i=a;i<=b;i++) 5 #define mst(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 typedef pair<int,int>P; 8 9 const int N=1e5+200,DEG=18;10 int g[N],v[N*2],nxt[N*2],ed,n,m,q,eed,cnt,id[N],Q[N];11 int dep[N],fa[N][DEG],dfn[N],idx,d[201][N];12 P vec[N];13 bool vis[N];14 15 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}16 inline void up(int &a,int b){if(a>b)a=b;}17 18 void dfs(int u=1,int pre=0)19 {20 dep[u]=dep[pre]+1,fa[u][0]=pre,dfn[u]=++idx;21 F(i,1,DEG-1)fa[u][i]=fa[fa[u][i-1]][i-1];22 for(int i=g[u];i;i=nxt[i])if(!dfn[v[i]])dfs(v[i],u);23 else if(v[i]!=pre&&dfn[v[i]]<dfn[u])vec[++eed]=P(u,v[i]);24 }25 26 int LCA(int a,int b){27 if(dep[a]>dep[b])a^=b,b^=a,a^=b;28 if(dep[a]<dep[b])F(i,0,DEG-1)if((dep[b]-dep[a])&(1<<i))b=fa[b][i];29 if(a!=b)for(int i=DEG-1;i<0?a=fa[a][0]:0,i>=0;i--)30 if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];31 return a;32 }33 34 void bfs(int *d,int S)35 {36 mst(vis,0);37 int head=1,tail=0,now;38 Q[++tail]=S,vis[S]=1,d[S]=0;39 while(head<=tail)for(int i=g[now=Q[head++]];i;i=nxt[i])40 if(!vis[v[i]])vis[v[i]]=1,d[v[i]]=d[now]+1,Q[++tail]=v[i];41 }42 43 int main()44 {45 while(~scanf("%d%d%d",&n,&m,&q))46 {47 int x,y;ed=idx=eed=cnt=0;48 mst(g,0),mst(dfn,0),mst(fa,0),mst(id,0);49 F(i,1,m)scanf("%d%d",&x,&y),adg(x,y),adg(y,x);50 dfs();51 F(i,1,eed)52 {53 if(!id[vec[i].first])id[vec[i].first]=++cnt,bfs(d[cnt],vec[i].first);54 if(!id[vec[i].second])id[vec[i].second]=++cnt,bfs(d[cnt],vec[i].second);55 }56 F(i,1,q)57 {58 scanf("%d%d",&x,&y);59 int ans=dep[x]+dep[y]-2*dep[LCA(x,y)];60 F(j,1,eed)61 {62 int u=id[vec[j].first],v=id[vec[j].second];63 up(ans,d[u][x]+d[v][y]+1),up(ans,d[v][x]+d[u][y]+1);64 }65 printf("%d\n",ans);66 }67 }68 return 0;69 }
2016弱校联盟十一专场10.2——Floyd-Warshall
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。