#PQJ121x553. QOJ 121_553

    ID: 2574 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2017最短路径并查集

QOJ 121_553

第一轮第一试 王国 王国 【故事背景】 JSOI 是一个有着高度发达科技的王国。近日,传送技术的出现大大便利了 人们的出行。国王JS 把评价王国交通体系的任务交给了交通大臣JYY。 【问题描述】 JSOI 王国由N 座城市组成,城市之间通过传送隧道相连。为了防止出现无 限传送的循环,任意两座城市之间有且仅有一条通过传送隧道连通的路径。第i 条隧道连通了城市ui 和vi,并需要ti 时间来通过。 第i 座城市内部共有mi 个节点,由mi-1 个居住节点环绕着一个传送节点构 成。不妨将外围的居住节点用1 到mi-1 编号。其中第j 号居住节点和下一个编号 的居住节点之间存在着长度为lij 的双向道路(第mi-1 号节点与1 号节点相邻,组 成一个居住环)。每个居住节点都向传送节点有一条双向道路,长度是cij。 对于同一座城市内的两个居住节点,它们可以经过城市内的其他节点相互到 达(可以途径该城市的传送节点,但不能使用传送节点传送到其他城市)。对于属 于不同城市的两个居住节点,则需要先到达初始城市的传送节点,经过一系列传 送隧道后到达目标城市的传送节点再经过城市内的道路到达目的地。 现在交通大臣JYY 想计算所有居住节点对之间的最短路径的长度和。由于 这个数字可能非常大,你只需要输出其模109+7 的值即可。 【输入格式】 从文件kingdom.in 中读入数据。 第一行包含一个正整数N。表示JSOI 的总城市个数。 接下来N-1 行,第i 行包含三个正整数ui,vi 和ti,表示编号ui 和vi 的城市 之间存在通行时间为ti 的传送隧道。 接下来3N 行,每3 行描述一个城市内部的节点信息。 其中第一行包含一个正整数mi,第i 个城市内部的节点数。 其中第二行包含mi-1 个正整数lij,第i 个城市内编号为j 和下一个的居住节 点之间的道路长度。 其中第三行包含mi-1 个正整数cij,第i 个城市内编号为j 的居住节点和该城 市传送节点之间的道路长度。 【输出格式】 输出到文件kingdom.out 中。 输出一行一个正整数,表示所有居住节点对之间的最短路径的长度和模 109+7 的值。

第一轮第一试 王国 【样例输入】 3 1 2 50 2 3 59 4 24 41 93 10 66 43 4 88 28 41 4 30 13 5 4 10 61 100 70 58 34 79 【样例输出】 10132 【数据规模与约定】 对于20%的数据满足0 < (𝑚% −1) ≤100; 对于另外20%的数据满足𝑚% = 3; 对于另外10%的数据满足𝑁= 1; 对于100%的数据满足1 ≤𝑁≤10-, 𝑚% ≥3, 0 < (𝑚% −1) ≤5×10-, 0 < 𝑡%, 𝑙%4, 𝑐%4 ≤106。