问题 D: Transit Tree Path
You are given a tree with N vertices.
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N−1 edges, where N is the number of its vertices.
The i-th edge (1≤i≤N−1) connects Vertices ai and bi, and has a length of ci.
You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):
find the length of the shortest path from Vertex xj and Vertex yj via Vertex K.
Constraints
3≤N≤105
1≤ai,bi≤N(1≤i≤N−1)
1≤ci≤109(1≤i≤N−1)
The given graph is a tree.
1≤Q≤105
1≤K≤N
1≤xj,yj≤N(1≤j≤Q)
xj≠yj(1≤j≤Q)
xj≠K,yj≠K(1≤j≤Q)
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N−1 edges, where N is the number of its vertices.
The i-th edge (1≤i≤N−1) connects Vertices ai and bi, and has a length of ci.
You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):
find the length of the shortest path from Vertex xj and Vertex yj via Vertex K.
Constraints
3≤N≤105
1≤ai,bi≤N(1≤i≤N−1)
1≤ci≤109(1≤i≤N−1)
The given graph is a tree.
1≤Q≤105
1≤K≤N
1≤xj,yj≤N(1≤j≤Q)
xj≠yj(1≤j≤Q)
xj≠K,yj≠K(1≤j≤Q)
输入
Input is given from Standard Input in the following format:
N
a1 b1 c1
:
aN−1 bN−1 cN−1
Q K
x1 y1
:
xQ yQ
N
a1 b1 c1
:
aN−1 bN−1 cN−1
Q K
x1 y1
:
xQ yQ
输出
Print the responses to the queries in Q lines.
In the j-th line j(1≤j≤Q), print the response to the j-th query.
In the j-th line j(1≤j≤Q), print the response to the j-th query.
样例输入
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5
样例输出
3
2
4
提示
The shortest paths for the three queries are as follows:
Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3
Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2
Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4
题意:求两个点经过k点之后的最短距离
HUST得训练赛上遇到得题目,直接dfs求出k点到各个点的最短距离就可以,输出的时候输出到两点距离的和就ok
附上代码(已AC):
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 100005 #define ll long long struct Edge{ ll to; ll next; ll cost; }; Edge edge[MAX*2]; ll head[MAX]; ll dis[MAX]; void DFS(ll u,ll v,ll w) { dis[u]=w; for(ll i=head[u];i!=-1;i=edge[i].next) { ll to=edge[i].to; if(to==v) continue; DFS(to,u,w+edge[i].cost); } return ; } int main() { ll n,u,v,w,q,k; scanf("%lld",&n); ll cnt=0; memset(head,-1,sizeof(head)); for(ll i=1;i<=n-1;i++) { scanf("%lld%lld%lld",&u,&v,&w); edge[cnt].to=v; edge[cnt].cost=w; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].to=u; edge[cnt].cost=w; edge[cnt].next=head[v]; head[v]=cnt++; } scanf("%lld%lld",&q,&k); DFS(k,-1,0); while(q--) { scanf("%lld%lld",&u,&v); printf("%lld ",dis[u]+dis[v]); } return 0; }