问题 26852. -- 调查黑暗气息

26852: 调查黑暗气息

时间限制: 1 Sec  内存限制: 128 MB
献花: 98  解决: 98
[献花][花圈]

题目描述

在数码世界中有一个叫做“Radiation Zone”的区域,里面荒无人烟,仿佛遗迹一般。在这个区域中有N个城市(假设编号为从0N-1),每个城市中都有一定数量的辐能。有M条已知长度的道路连接它们,每条道路都可以双向来往。

近期这个区域似有黑暗气息蛰伏,国王Shoutmon派出调查队前来调查这个区域中的城市。调查队的飞船降落在S号城市。由于飞船降落时气流不稳定,因此产生了辐能波,导致以S号城市为中心的L层以内(假设S号城市为最内层,记为第0层)的城市的辐能都会上升(只上升一次),上升的数值为 “城市的当前辐能乘以百分比p”的向上取整。其中百分比pS号城市时为100%,且每向外扩散一层,百分比降低100%/L(例如,如果L5,那么第0层(即S号城市)为100%,第1层为80%,第2层为60%,第3层为40%,第4层为20%,其中百分比均为浮点数)。所谓第X层是指,连接某城市与S号城市的最少数量的道路数,例如下图是一个例子,图中的数字为其层号。

之后调查队需要前往T号城市调查。为了顺便清除城市中的辐能,他们准备了一个容量为K的辐能吸收器。辐能吸收器可以自动吸收城市中的辐能,且满容量时会自动将容器内的所有辐能都燃烧完毕,以继续吸收辐能。假设调查队总是把城市(含S号和T号城市)中的辐能吸收完毕。

为了节省体力,调查队希望选择一条长度最短的路径前往T号城市;如果这样的路径有多条,那么从中选择到达T号城市时辐能吸收器内当前辐能最大的路径;如果这样的路径仍然有多条,那么从中选择路径后半段的城市的辐能之和最小的路径(所谓后半段是指,如果路径上有m个城市,那么后m/2个城市(含T号城市)是后半段的城市。例如,如果路径上有7个城市,那么路径的后3个城市(除法为向下取整)为后半段的城市)。数据保证这样的路径一定唯一。

输入

每个输入文件中一组数据。

第一行六个整数NMLKST2<=N<=500, M<=N*(N-1)/2, 1<=L<=500, 2<=K<=100, S != T),分别代表城市个数、道路条数、辐能上升的层数、辐能吸收器的容量、起点城市编号、终点城市编号。

接下来一行有N个正整数,分别给出N个城市的初始辐能(均为不超过100的正整数)。

接下来M行,每行三个数字uvw,代表一条道路,其中uv为道路的两个端点城市编号,w为道路的长度(w为不超过1000的正整数)。数据保证u不等于v,且相同的无序对(u,v)只出现一次。

输出

如果从S号城市不能到达T号城市,那么只输出-1

如果从S号城市能到达T号城市,那么输出两行:

第一行输出四个整数, S号城市到T号城市的最短距离的路径条数(数据保证不超过100000条)、S号城市到T号城市的最短距离、通过最终选择的路径到达T号城市时辐能吸收器内的当前辐能、最终选择的路径的后半段城市的辐能之和。

第二行输出最终选择的路径,路径上的城市之间用->隔开。

样例输入

7 8 1 7 0 6
20 10 10 6 8 13 5
0 1 1
0 2 1
1 3 1
2 4 1
2 5 1
3 6 1
4 6 1
5 6 1

样例输出

3 3 5 11
0->1->3->6

提示

来源

[献花][花圈]