#P17974. Meeting for Meals

Meeting for Meals

Meeting for Meals

题目描述

校园用一个有 nn 个节点、mm 条带长度边的连通无向图表示。聚餐地点在节点 11。有 kk 位朋友同时从互不相同的节点出发,前往节点 11。

所有人的移动速度均为每单位时间走过单位长度。他们可以等待,也可以在一条边上的任意位置改变移动方向。

设 tmeett_{\mathrm{meet}} 为使所有朋友都能到达节点 11 的最早时刻。在所有人均须不晚于 tmeett_{\mathrm{meet}} 到达节点 11 的前提下,分别对每位朋友求出:从出发到时刻 tmeett_{\mathrm{meet}},他最多可以有多长的总时间与至少另一位朋友待在图上的同一个位置。这个位置可以是节点,也可以是边的内部。到达节点 11 后一起等待的时间同样计入。

对每位朋友的答案独立计算。计算第 ii 位朋友的答案时,可以为所有人安排最有利于第 ii 位朋友的移动与等待方案;不同答案不要求由同一套方案同时实现。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例中,第一行三个整数 n,m,kn,m,k。

第二行 kk 个互不相同的整数 a1,a2,…,aka_1,a_2,\ldots,a_k,表示各位朋友的出发节点。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示节点 u,vu,v 之间有一条长度为 ww 的无向边。

输出格式

每个测试用例输出一行 kk 个数,第 ii 个数为第 ii 位朋友最多能与人同行或共同等待的总时间。每个数必须恰好保留一位小数。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 2≤n≤3×1052\le n\le3\times10^5,n−1≤m≤106n-1\le m\le10^6,2≤k≤n2\le k\le n;
  • 1≤ai,u,v≤n1\le a_i,u,v\le n,u≠vu\ne v,1≤w≤1091\le w\le10^9;
  • 图连通,无重边、无自环,所有出发节点互不相同;
  • 所有测试用例的 nn 之和不超过 3×1053\times10^5,mm 之和不超过 10610^6。

样例

输入

3
4 3 2
3 4
1 2 3
3 2 1
4 2 1
2 1 2
1 2
1 2 3
3 2 3
1 2 3
1 2 3
1 3 5

输出

3.0 3.0
1.5 1.5
3.5 3.5 2.5

样例说明

第三组中,最早的集合时刻为 55。

从节点 11、22 出发的两人可以在时刻 1.51.5 于边 (1,2)(1,2) 的中点相遇,一起用 1.51.5 单位时间返回节点 11,再共同等待 22 单位时间。因此他们各自的最优答案都是 3.53.5。

从节点 33 出发的人,可以在时刻 2.52.5 于边 (1,3)(1,3) 的中点与从节点 11 出发的人相遇,再一起用 2.52.5 单位时间返回。因此他的答案为 2.52.5。