bet365体育app下载_外围bet365 网址_bet365娱乐在线先锋网?bet365体育app下载_外围bet365 网址_bet365娱乐在线片段及技术文章聚合

Contest1389 - 2018年第三阶段个人训练赛第四场. Transit Tree Path(DFS)

技术标签:?Contest1389 - 2018年第三阶段个人训练赛第四??Transit Tree Path??DFS

问题 D: Transit Tree Path

时间限制:?1 Sec??内存限制:?128 MB
提交:?515??解决:?152
[提交] [状态] [讨论版] [命题人:admin]

题目描述

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)

?

输入

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

?

?

输出

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.

?

样例输入

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

考点:DFS


#include
#include
using namespace std;
long long dist[100005];
vector<> > G[100005];
int N,a,b,c,Q,K;
int dfs(int nod)
{
    for(auto it:G[nod])
    {
        if(!dist[it.first]){
            dist[it.first]=dist[nod]+it.second;
            dfs(it.first);
        }
    }
}
int main()
{
    cin>>N;
    for(int i=1; i>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    cin>>Q>>K;
    dist[K]=1;
    dfs(K);
    while(Q--)
    {
        cin>>a>>b;
        cout<

?

原文地址:Contest1389 - 2018年第三阶段个人训练赛第四场. Transit Tree Path(DFS)