这道题与之前那两道模板题不同的是，路径有了权值，而且边是双向的，root已经给出来了，就是1，（这个地方如果还按之前那样来计算入度是会出错的。数据里会出现多个root。。。数据地址可以在poj的discuss板块看到）。两个节点之间的距离，可以这样处理：先处理出每个节点i到根的距离dist[i]，则节点a,b之间的距离就是dist[a]+dist[b]-2*dist[LCA(a,b)]，或者是在LCA的过程中加一个形式变量来传递距离值（目测这样效率会更高）。我一开始是想的仅传递每层的距离，具体怎样记不清了，结果样例就华丽丽地wa了。个人认为这个题目描述真心不爽。最后那个方向字符在这个题中没用。
#include<cstdio>
#include<vector>
#include<string>
//sba,just predeal the distance between every node and the root.and the dist[u][v]=dist[u][root]+dist[v][root]-2*dist[x][root]
using namespace std;
;
;
;
struct node{
int v,dis;
node(){v=;dis=;}
};
int ansque[MAXQUERY];
int father[MAXN];//i's ancestor and the distance between the son and the ancestor
vector<node>map[MAXN];
vector<node>query[MAXN];
int dist[MAXN];//i -->root
bool visit[MAXN],visit2[MAXN];
int getfather(int v){
if(father[v]==v)return v;
return father[v]=getfather(father[v]);
}
void aunion(int u,int v){
int fu=father[u],fv=father[v],di;
father[fv]=fu;
}
void LCA(int id,int distance){
int len=map[id].size();
int son;
visit2[id]=;
dist[id]=distance;
;i<len;i++){
son=map[id][i].v;
if(!visit2[son]){
LCA(son,distance+map[id][i].dis);
aunion(id,son);
}
}
visit[id]=true;
len=query[id].size();
;i<len;i++){
son=query[id][i].v;
if(visit[son]){
ansque[query[id][i].dis]=dist[id]+dist[son]-*dist[father[getfather(son)]];
//mark
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){//attention
//at the begining,we'd better to initialize all the vars
int x,y,l;
char a;
node b;
;i<=n;i++){
map[i].clear();//the mothod of the initialization of queue
query[i].clear();
father[i]=i;
visit[i]=;
visit2[i]=;
ansque[i]=;
dist[i]=;
}
while(m--){
scanf("%d %d %d %c",&x,&y,&l,&a);//only father
b.v=y;b.dis=l;
map[x].push_back(b);
b.v=x;
map[y].push_back(b);
}
scanf("%d",&m);
node tmp2;
;i<m;i++){
scanf("%d%d",&x,&y);
tmp2.v=y;tmp2.dis=i;
query[x].push_back(tmp2);
tmp2.v=x;
query[y].push_back(tmp2);
}
LCA(,);
;i<m;i++)
printf("%d\n",ansque[i]);
}
;
}