题目大意：给出n个城市，m条路，不存在环，求任意两个城市间的距离，城市间可能不联通
解题思路：ST+并查集， 并查集判断城市间是否联通，因为给出的可能是森林，将每颗树的根节点指向一个root，构成一棵树。
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <queue> #include <set> #include <string> #include <cctype> #include <vector> #include <algorithm> using namespace std; const int N = 10010; const int M = 25; const int INF = 99999999; struct Edge{ int node,len; Edge*next; }m_edge[N*2]; int Ecnt; Edge*head[N]; int tot,ver[2*N],R[2*N],first[N],dir[N]; bool vis[N]; int dp[2*N][M]; int father[N]; //ver:节点编号 R：深度 first：点编号位置 dir：距离 void dfs(int u ,int dep) { vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep; for( Edge*k=head[u]; k ; k = k->next ) if( !vis[k->node] ){ int v = k->node , w = k->len; dir[v] = dir[u] + w; dfs(v,dep+1); ver[++tot] = u; R[tot] = dep; } } //对R进行预处理，保存的是R的编号 void ST(int n) { for(int i=1;i<=n;i++) dp[i][0] = i; for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ int a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1]; dp[i][j] = R[a]<R[b]?a:b; } } } //中间部分是交叉的。 int RMQ(int l,int r) { int k=0; while((1<<(k+1))<=r-l+1) k++; int a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号 return R[a]<R[b]?a:b; } int LCA(int u ,int v) { int x = first[u] , y = first[v]; if(x > y) swap(x,y); int res = RMQ(x,y); return ver[res]; } void init() { Ecnt = tot = 0; fill( head , head+N , (Edge*)0 ); fill( vis , vis+N , false ); for( int i = 0 ; i < N ; ++i ) father[i] = i; } int find( int a ) { int t = a; while( father[t] != t ){ father[t] = father[father[t]]; t = father[t]; } return t; } void merge( int a , int b ) { int t1 = find( a ); int t2 = find( b ); if( t1 != t2 ) father[t1] = t2; } void mkEdge( int a , int b , int c ) { m_edge[Ecnt].node = a; m_edge[Ecnt].len = c; m_edge[Ecnt].next = head[b]; head[b] = m_edge + Ecnt++; m_edge[Ecnt].node = b; m_edge[Ecnt].len = c; m_edge[Ecnt].next = head[a]; head[a] = m_edge + Ecnt++; } int main() { int n,m,p,a,b,c; while( ~scanf("%d%d%d",&n,&m,&p) ){ init(); for( int i = 0 ; i < m ; ++i ){ scanf("%d%d%d",&a,&b,&c); mkEdge( a , b , c ); merge( a , b ); } for( int i = 1 ; i <= n ; ++i ){ if(father[i]!=i) continue; mkEdge( 0 , i , 0 ); //root为0，长度为0 } dir[0] = 0; dfs( 0 , 1 ); ST( 2*(n+1)-1 ); for( int i = 0 ; i < p ; ++i ){ scanf("%d%d",&a,&b); if( find(a) != find(b) ){ printf("Not connected\n"); continue; } c = LCA(a,b); printf("%d\n",dir[a]+dir[b]-2*dir[c]); } } return 0; }
