2018.7中石油个人赛第4场(D-Transit Tree Path)-最短路算法

6690: Transit Tree Path

时间限制: 1 Sec 内存限制: 128 MB
提交: 472 解决: 132
[提交] [状态] [讨论版] [命题人: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≤10⁵
1≤ai,bi≤N(1≤i≤N−1)
1≤ci≤10⁹(1≤i≤N−1)
The given graph is a tree.
1≤Q≤10⁵
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
:
a_N−1 b_N−1 c_N−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.

样例输入

样例输出

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

  1 /*
  2 题意 : 
  3     求结点x经过结点k到达结点y的最短距离
  4     转化为以k结点为起始点,求k分别到结点x和结点y的最短距离
  5     用到SPFA算法
  6 */
  7 //赛后补题,一开始将dist[]的值赋值为INF,wa了
  8 //后来想了一下,INF值为1061109567
  9 //虽然大于1e9,但时如果两条边都是1e9,则加和就>INF,此时就会出错
 10 //所以需要用LINF来个dist[]中的数组初始化为无穷大
 11 //一定要判断清除用哪个
 12 #include<iostream>
 13 #include<cstdio>
 14 #include<cstring>
 15 #include<queue>
 16 #include<vector>
 17 using namespace std;
 18 #define INF 0x3f3f3f3f
 19 #define LINF 0x3f3f3f3f3f3f3f3f
 20 const int maxn=1e5+1;
 21 typedef long long type_weight;
 22 struct Edge
 23 {
 24     //根据题意定义weight的类型
 25     //可能为long long 型,也可能为int型
 26     //用typedef定义type_weight,方便修改类型
 27     int vex;
 28     type_weight weight;
 29     Edge(int v=0,type_weight w=0):vex(v),weight(w){}
 30 };
 31 vector<Edge>E[maxn];
 32 
 33 //向E[u]中加入(v,weight) : 边u与边v相连,其权值为weight
 34 void addedge(int u,int v,type_weight weight)
 35 {
 36     E[u].push_back(Edge(v,weight));
 37 }
 38 //visited[i] : 判断结点i是否在队列中
 39 //dist[] : 存储最短距离,最好定义成long long 型
 40 //cnt[] : 判断是否存在负环
 41 bool visited[maxn];
 42 long long dist[maxn];
 43 int cnt[maxn];
 44 //求从start结点到其他结点的最短距离
 45 //共n个结点
 46 bool SPFA(int start,int n)
 47 {
 48     memset(visited,0,sizeof(visited));
 49     //初始化dist[]为LINF,即长整型的最大值(无穷大)
 50     for(int i=1;i<=n;i++)
 51         dist[i]=LINF;
 52     dist[start]=0;
 53     visited[start]=true;
 54 
 55     queue<int >que;
 56     while(!que.empty())
 57         que.pop();
 58     que.push(start);
 59 
 60     while(!que.empty())
 61     {
 62         int u=que.front();
 63         que.pop();
 64 
 65         //遍历以u为弧尾的所有结点
 66         //E[u][i].v : 以u为弧尾的结点
 67         //E[u][i].weight : 结点u与结点E[u][i].v之间的权重
 68         for(int i=0;i<E[u].size();i++)
 69         {
 70             int v=E[u][i].vex;
 71 
 72             //判断边u是否能松弛边v
 73             if(dist[v] > dist[u]+E[u][i].weight)
 74             {
 75                 dist[v]=dist[u]+E[u][i].weight;
 76                 if(!visited[v])
 77                 {
 78                     que.push(v);
 79                     visited[v]=true;
 80                     //如果某个结点进入队列的此数超过n-1次,则此图存在负环
 81                     if(++cnt[v] > n)
 82                         return false;
 83                 }
 84             }
 85         }
 86     }
 87     return true;
 88 }
 89 
 90 int main()
 91 {
 92     int N;
 93     scanf("%d",&N);
 94     for(int i=1;i<N;i++)
 95     {
 96         int a,b;
 97         type_weight weight;
 98         scanf("%d%d%lld",&a,&b,&weight);
 99         addedge(a,b,weight);
100         addedge(b,a,weight);
101     }
102     int Q,K;
103     scanf("%d%d",&Q,&K);
104     SPFA(K,N);
105     for(int i=1;i<=Q;i++)
106     {
107         int x,y;
108         scanf("%d%d",&x,&y);
109         printf("%lld
",dist[x]+dist[y]);
110     }
111     return 0;
112 }