2.28模拟题 problem4 调查黑暗气息

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

近期这个区域似有黑暗气息蛰伏,国王Shoutmon派出调查队前来调查这个区域中的城市。调查队的飞船降落在S号城市。由于飞船降落时气流不稳定,因此产生了辐能波,导致以S号城市为中心的L层以内(假设S号城市为最内层,记为第0层)的城市的辐能都会上升(只上升一次),上升的数值为 “城市的当前辐能乘以百分比p”的向上取整。其中百分比p在S号城市时为100%,且每向外扩散一层,百分比降低100%/L(例如,如果L为5,那么第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个城市(除法为向下取整)为后半段的城市)。数据保证这样的路径一定唯一。

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

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

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

接下来M行,每行三个数字u、v、w,代表一条道路,其中u和v为道路的两个端点城市编号,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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
//N、M、L、K、S、T(2<=N<=500, M<=N*(N-1)/2, 1<=L<=500, 2<=K<=100, S != T),分别代表城市个数、道路条数、辐能上升的层数、辐能吸收器的容量、起点城市编号、终点城市编号
const int maxn = 510;
const int INF = 1000000000;
int n, m, l, k, s, t;
int weight[maxn], G[maxn][maxn], d[maxn];
int numPath = 0, remainK = -1, halfSumK = INF;
bool inq[maxn] = {false}, vis[maxn] = {false};
vector<int> tempPath, path;
vector<int> pre[maxn];
struct node{
int layer;//层数
int id;
};
void init(){
fill(G[0], G[0]+ maxn * maxn, INF);
numPath = 0;
remainK = -1;
halfSumK = INF;
memset(vis, false, sizeof(vis));
memset(inq, false, sizeof(inq));
for (int i = 0; i < maxn; i++) {
pre[i].clear();
}
tempPath.clear();
path.clear();
}
void DFS(int v){
if (v == s) {
tempPath.push_back(v);
numPath++;
int tempW = 0, temphalfSumK = 0;
for (int i = 0; i < (int)tempPath.size() / 2; i++) {
int id = tempPath[i];
tempW += weight[id];
temphalfSumK += weight[id];
}
for (int i = (int)tempPath.size() / 2; i < tempPath.size(); i++) {
int id = tempPath[i];
tempW += weight[id];
}
if (tempW % k > remainK) {
remainK = tempW % k;
halfSumK = temphalfSumK;
path = tempPath;
}else if(tempW % k == remainK ){
if (temphalfSumK < halfSumK) {
halfSumK = temphalfSumK;
path = tempPath;
}
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for (int i = 0; i < pre[v].size(); i++) {
DFS(pre[v][i]);
}
tempPath.pop_back();
}
void Dijstra(int s){
fill(d, d + maxn, INF);
for (int i = 0; i < n; i++) {
pre[i].push_back(i);//初始化路径
}
d[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1, MIN = INF;
for (int j = 0; j < n; j++) {
if (vis[j] == false && d[j] < MIN) {
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = true;
for (int v = 0; v < n; v++) {
if (vis[v] == false && G[u][v] != INF) {
if (d[u] + G[u][v] < d[v] ) {
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[u] + G[u][v] == d[v]){
pre[v].push_back(u);
}
}
}
}
}
void BFS(int s){//BFS解决污染扩散问题
node start;
start.id = s;
start.layer = 0;
queue<node> q;
q.push(start);
inq[start.id] = true;
while (!q.empty()) {
node now = q.front();
q.pop();
int u = now.id;
if (now.layer < l) {
weight[u] += (int)(ceil(weight[u] * 1.0 * (l - now.layer) / l ) + 0.5);
}
for (int v = 0; v < n; v++) {
if (inq[v] == false && G[u][v] != INF) {
node next;
next.id = v;
next.layer = now.layer + 1;
q.push(next);
inq[v] = true;
}
}

}
}

int main() {
init();
scanf("%d%d%d%d%d%d", &n, &m, &l, &k, &s, &t);
for (int i = 0; i < n; i++) {
scanf("%d", &weight[i]);
}
int u, v, w;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
BFS(s);
if(inq[t] == false){
printf("-1\n");
return 0;
}
Dijstra(s);
DFS(t); //获取最优路径
printf("%d %d %d %d\n", numPath, d[t], remainK, halfSumK);
for(int i = path.size() - 1; i >= 0; i--) {
printf("%d", path[i]); //倒着输出路径上的结点
if(i > 0) printf("->");
else printf("\n");
}
return 0;
}