|
虚拟赛的时候一看是求任意两点的最短路不管怎么优化都超时最近做一些树的题目这是求任意两点到最近公共祖先的距离先用并差集判断是否联通联通就求最近公共祖先先把图建成一棵棵树 #include<stringh> #include<stdioh> #define N int father[N]dfs[N]nvis[N]head[N]numf[N]ansdis[N]; struct edge { int stednextw; }E[N*]; void addedge（int xint yint w） { E[num]st=x; E[num]ed=y; E[num]w=w; E[num]next=head[x]; head[x]=num++; } int find（int a） { if（f[a]!=a） f[a]=find（f[a]） return f[a]; } void dfs（int u） { int iv; vis[u]=; for（i=head[u];i!=;i=E[i]next） { v=E[i]ed; if（vis[v]==）continue; father[v]=u; dfs[v]=dfs[u]+; dis[v]=E[i]w; dfs（v） } if（ans<dfs[u]） ans=dfs[u]; } int LCA（int xint y） { int sum=; while（dfs[x]>dfs[y]） { sum+=dis[x]; x=father[x]; } while（dfs[y]>dfs[x]） { sum+=dis[y]; y=father[y]; } while（x!=y） { sum+=（dis[x]+dis[y]） x=father[x]; y=father[y]; } return sum; } int main（） { int ijkxymansw; while（scanf（%d%d%d&n&m&k）！=） { memset（headsizeof（head）） num=; for（i=;i<=n;i++） f[i]=i; for（i=;i<m;i++） { scanf（%d%d%d&x&y&w） addedge（xyw） addedge（yxw） x=find（x） y=find（y） if（x!=y） f[x]=find（y） } memset（vissizeof（vis）） ans=; for（i=;i<=n;i++） { if（vis[i]==） { dis[i]=; dfs[i]=ans; father[i]=i; dfs（i） ans++; } } while（k） { scanf（%d%d&x&y） if（find（x）！=find（y）） {printf（Not connected\n）continue;} j=LCA（xy） printf（%d\nj） } } return ; } |
