给出n个区域,有n-1条路去连接这些区域,显然他是一个带权无根树。首先把它以0为根看成有根树,对于给出的三个点,每两个点之间的距离是固定的,因为他们之间只有一条路,但是对于这么多查询(at most 70000 ),直接找距离代价太大,找出每两个点的LCA,这样就可以两个点之间的距离了,(需要知道从0点开始到这两个点的距离)。 我们把这三对点的距离加起来再除以2,就能得到连接着三个点的最短路径。
#include<string> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #include<algorithm> #include<climits> #include<map> #include<vector> const int maxn = 50000; using namespace std; class Node{ public: int to,w; Node *next; void add( int tt,int ww,Node *&b ){ to = tt;w= ww;next = b;b=this; } }; int ab(int a,int b){return a>b?(a-b):(b-a);} Node *biao[ maxn ],a[ maxn*3 ]; int TIME,countt,N; int founder[ maxn ]; int timepoint[ maxn*2 ]; int timedeep [ maxn*2 ]; int opt[ maxn*2 ][ 20 ]; int flag[ maxn ]; int d[ maxn ]; int o[ 3 ]; void dfs( int u,int deep ){ timedeep[ founder[u] = TIME++ ] = deep; timepoint[ TIME-1 ] = u; flag[u] = 1; for( Node*p=biao[u]; p != NULL; p = p->next ) if( !flag[p->to] ){ d[p->to] = d[u] + p->w; dfs( p->to , deep +1 ); timepoint[TIME++] = u; timedeep[TIME-1]= deep; } } //这个dfs计算时间戳,顺便计算每个点到0点的距离 int main(void){ int i,from,m,to,w; int j,tt,minn,countt; int start,end,k,s = 0; while( scanf("%d",&N) != EOF ){ if( s++ ) cout << endl; for( i = 0; i < N; i++ ) biao[i] = NULL; countt = 0; for( i = 1; i < N; i++ ){ scanf("%d%d%d",&from,&to,&w); a[countt++].add( to,w,biao[from] ); a[countt++].add( from,w,biao[to] ); } for( i = 0; i < N; i++ ) flag[i] = 0; d[0] = 0; TIME = 0; dfs( 0,0 ); for( i = 0; i < 2*N -1 ; i++ ) opt[i][0] = i; for( j = 1; (1<<j) <= 2*N-1; j++ ){ tt = 1<<j; for( i = 0; i + tt -1 < 2*N -1 ; i++ ){ if( timedeep[ opt[i][j-1] ] < timedeep[ opt[i+tt/2][j-1] ] ) opt[i][j] = opt[i][j-1]; else opt[i][j] = opt[i+tt/2][j-1]; } } //应该是st算法吧,这个dp实在是太神奇了。。 cin >> m; while( m-- ){ scanf("%d%d%d",&o[0],&o[1],&o[2]); minn = 0; for( i = 0; i < 3; i++ ){ start = min( founder[o[i]], founder[o[(i+1)%3]] ); end = max( founder[o[i]], founder[o[(i+1)%3]] ); k = (int)( log(end-start+1)/log(2) ); if( timedeep[ opt[start][k] ] < timedeep[ opt[end-(1<<k)+1][k] ] ) tt = opt[start][k] ; else tt = opt[end-(1<<k)+1][k] ; k = d[ timepoint[start] ] - d[timepoint[tt]]; k += d[timepoint[end] ] - d[timepoint[tt]]; minn += k; } printf("%d\n",minn/2); } } return 0; }
可以先用floyd暴力 再直接查询,不过数据太大 = =、