题目大意：
求三点之间的最短距离
思路：
有了两点之间的最短距离求法，不难得出：
对于三个点我们两两之间求最短距离 得到 d1 d2 d3
那么最短距离就是 d = ( d1 + d2 + d3 ) / 2
- 要注意每个数组的范围大小，因为这个问题手抖敲错，TLE+RE一整页/(ㄒoㄒ)/~~
- 用前向星来保存边和询问，空间卡的也很严
- 如下图所示：所求路线为紫色，等于蓝色+黄色+绿色之和的一半
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
const int maxm = 70005;
struct node1 {
int next,to,w;
} e[maxn*2];
struct node2 {
int next,to,id;
} q[maxm*6];
int n,m,head1[maxn],head2[maxn],cnt1,cnt2,vis[maxn],f[maxn],res[maxm*6],dist[maxn];
inline void add1(int u, int v, int w) {
e[cnt1].to=v;
e[cnt1].w=w;
e[cnt1].next=head1[u];
head1[u]=cnt1++;
}
inline void add2(int u, int v, int id) {
q[cnt2].to=v;
q[cnt2].id=id;
q[cnt2].next=head2[u];
head2[u]=cnt2++;
}
inline void init() {
cnt1=cnt2=0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(vis,0,sizeof(vis));
}
inline int Find(int x) {
return x == f[x] ? x : f[x] = Find(f[x]);
}
inline void tarjan(int s) {
vis[s]=1;
f[s]=s;
int t;
for(int i=head1[s]; i!=-1; i=e[i].next) {
if(!vis[t=e[i].to]) {
dist[t]=dist[s]+e[i].w;
tarjan(t);
f[t]=s;
}
}
for(int i=head2[s]; i!=-1; i=q[i].next)
if(vis[t=q[i].to])
res[q[i].id]=dist[s]+dist[t]-2*dist[Find(t)];
}
int main() {
int cnt=0,u,v,w,x,y,z;
while(~scanf("%d",&n)) {
init();
for(int i=1; i<n; ++i) {
scanf("%d %d %d",&u,&v,&w);
add1(u,v,w);
add1(v,u,w);
}
scanf("%d",&m);
m*=3;
for(int i=1; i<=m; ++i) {
scanf("%d %d %d",&x,&y,&z);
add2(x,y,i);
add2(y,x,i);
++i;
add2(x,z,i);
add2(z,x,i);
++i;
add2(y,z,i);
add2(z,y,i);
}
dist[0]=0;
tarjan(0);
if(!cnt) cnt++;
else printf("
");
for(int i=1; i<=m; ++i) {
printf("%d
",(res[i]+res[i+1]+res[i+2])/2);
i+=2;
}
}
return 0;
}