# POJ PKU 1986 Distance Queries 解题报告

PS：那个输入的方向C完全没用，仅仅是为了和1984题保持输入格式一致

```#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
node(){first = -1;}
long dis;
long first;
};

{
long next, to, dis;
};

//并查集个人模板
long DSet[50005];
void init(long n)
{
for( long i = 0 ; i <= n ; i ++)
DSet[i] = i;
}
long findP( long id)
{
if(DSet[id] != id)
DSet[id] = findP(DSet[id]);
return DSet[id];
}
//联合元素，这里修改为把b的父节点设为a，但是要在下面使用的时候注意不能搞反顺序
long UnionEle( long a, long b)
{
a = findP(a);
b = findP(b);
DSet[b] = a;
return a;
}

void lca(long pos, long dis);

bool ischeck[50005] = {false};
long res[20005] = {0};
long que[50005];
node point[50005];

void insertR(long from, long to, long len, long &n)
{
rd[n].to = to;
rd[n].dis = len;
rd[n].next = point[from].first;
point[from].first = n;
n ++;
}
void insertQ(long from, long to, long index, long &n)
{
question[n].to = to;
question[n].dis = index;
question[n].next = que[from];
que[from] = n;
n ++;
}
int main()
{
long n, m, i, j, k, from, to, len, rdl = 0, quel = 0;
char c;
scanf("%ld %ld", &n, &m);

for(i = 0; i < m; i ++)
{

scanf("%ld %ld %ld %c", &from, &to, &len, &c);
insertR(from, to, len, rdl);
insertR(to, from, len, rdl);
}

memset(que, -1, sizeof(que));
scanf("%ld", &k);
//Input question
for(i = 0; i < k; i ++)
{
scanf("%ld %ld", &from, &to);
insertQ(from, to, i, quel);
insertQ(to, from, i, quel);
}

init(n);
ischeck[1] = true;
lca(1, 0);
for(i = 0; i < k; i ++)
printf("%ld\n", res[i]);
return 0;
}

void lca(long pos, long dis)
{
point[pos].dis = dis;
long i, p;
ischeck[pos] = true;
for(i = point[pos].first; i != -1; i = rd[i].next)
{
if(ischeck[rd[i].to] == false)
{
lca(rd[i].to, dis + rd[i].dis);
UnionEle(pos, rd[i].to);
}
}

for(i = que[pos]; i != -1; i = question[i].next)
{
if(ischeck[question[i].to])
{
p = findP(question[i].to);
res[question[i].dis] = dis + point[question[i].to].dis  - 2 * point[p].dis;
}
}
}```

167 篇文章28 人订阅

0 条评论

## 相关文章

### 阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

1402

933

### Leetcode 130 Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions su...

1965

1661

1603

3355

### TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

1644

### HashMap扩容拾遗

JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题，本篇将对这两个知识点进行小结。

1112

922

### tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

4956