#P4158. [POI2007]Railway

    ID: 3373 传统题 1000ms 32MiB 尝试: 26 已通过: 14 难度: 7 上传者: 标签>难度分类提高+/省选-图论DijkstraPrim枚举与搜索路径恢复欧拉回路Steiner 树度量闭包近似CF2200

[POI2007]Railway

[POI 2007] Railway

题目描述

比特国要缩减铁路网络。铁路网原本连通,每条铁路双向通行,有一个正整数维护费用。现在指定若干座必须保留的车站,要求只保留一部分铁路,使任意两座指定车站仍能相互到达。保留的铁路可以经过其他车站。

设使所有指定车站连通所需的最小总维护费用为 Cmin⁡C_{\min}。输出一组总费用不超过 2Cmin⁡2C_{\min} 的铁路。保留的铁路应位于同一个连通部分,并与所有指定车站相连。

输入格式

第一行两个整数 n,mn,m(2≤n≤5 0002\le n\le5\,000,1≤m≤500 0001\le m\le500\,000),表示车站数和铁路数。车站从 11 到 nn 编号,任意两座不同车站间至多有一条铁路。

保证 m≤n(n−1)/2m\le n(n-1)/2。接下来 mm 行,每行三个整数 u,v,wu,v,w(1≤u,v≤n1\le u,v\le n,u≠vu\ne v,1≤w≤1051\le w\le10^5),表示一条维护费用为 ww 的双向铁路。

最后一行先给出整数 pp(1≤p≤n1\le p\le n,mp≤15 000 000mp\le15\,000\,000),随后按升序给出 pp 座必须保留的车站的编号。

输出格式

第一行两个整数 c,kc,k,分别为所选铁路的总维护费用和条数。接下来 kk 行,每行两个整数,表示一条所选铁路的两个端点。可以输出任意符合要求的方案。

样例 #1

样例输入 #1

8 11
1 2 6
3 1 5
2 3 8
3 4 9
3 5 10
5 4 3
5 6 9
6 4 8
6 8 8
6 7 7
8 7 10
4 2 5 7 8

样例输出 #1

42 5
2 3
3 5
5 6
6 7
6 8

样例说明

图中实心圆是必须保留的车站,粗线为样例选出的铁路。

样例车站与铁路,粗线为所选方案