地铁一日游
时间限制: 550 ms
内存限制: 64 MB
森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！
魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每 K 公里增加 1 元车费。
例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为 2 + 4 = 6 元。
为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。
坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？
地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都 1 号线和 2 号线都经过人民广场站，则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。
输入格式：
输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤ K ≤ 10^6)，加 1 元车费。
接下来 M 行，每行由以下格式组成：
<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>
其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 10^6 的正整数。一条线路上的站点互不相同。
注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。
再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。
最后有 Q 行，每行一个正整数 Xi，表示森森尝试从编号为 Xi 的站点出发。
输出格式：
对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。
输入样例:1
2
3
4
5
6
7
86 2 6
1 6 2 4 3 1 4
5 6 2 6 6
4
2
3
4
5
输出样例:1
2
3
41 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 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
int main(void)
{
int n, m, k, i, j, a;
scanf("%d %d %d", &n, &m, &k);
//Init D
int D[n][n];
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
D[i][j] = (i == j ? 0 : -1);
//Get D
int s1, s2, len, terminal[m*2];
char ch;
for(i = 0; i < m; ++i)
{
scanf("%d", &s1);
s1--;
terminal[i*2] = s1;
ch = getchar();
while(ch != '\n')
{
scanf("%d %d", &len, &s2);
s2--;
if(D[s1][s2] == -1 || D[s1][s2] > len)
{
D[s1][s2] = len;
D[s2][s1] = D[s1][s2];
}
s1 = s2;
ch = getchar();
}
terminal[i*2 + 1] = s1;
}
//Floyd
for(a = 0; a < n; ++a)
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
if(D[i][a] != -1 && D[a][j] != -1)
if(D[i][j] == -1 || D[i][a] + D[a][j] < D[i][j])
D[i][j] = D[i][a] + D[a][j];
//Preprocess
int canArr[n][n];
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
canArr[i][j] = 0;
for(i = 0; i < n; ++i)
{
for(j = 0; j < m*2; ++j)
if(D[i][terminal[j]] != -1)
canArr[i][terminal[j]] = 1;
for(j = 0; j < n; ++j)
{
if(j != i)
{
if(D[i][j] == -1)
continue;
for(a = 0; a < n; ++a)
if(a != i && a != j)
if(D[i][a] != -1 && D[i][a] / k == D[i][j] / k && D[i][a] > D[i][j])
break;
if(a == n)
canArr[i][j] = 1;
}
}
}
//Solve Problem
int q, start, arr[n], queue[n], head, tail, flag;
scanf("%d", &q);
for(i = 0; i < q; ++i)
{
for(j = 0; j < n; ++j)
arr[j] = 0;
scanf("%d", &start);
arr[--start] = 1;
head = 0, tail = 0;
queue[0] = start;
while(head <= tail)
{
for(j = 0; j < n; ++j)
if(!arr[j] && canArr[queue[head]][j])
{
queue[++tail] = j;
arr[j] = 1;
}
head++;
}
flag = 0;
for(j = 0; j < n; ++j)
if(arr[j])
{
if(flag)
printf(" ");
else
flag = 1;
printf("%d", j+1);
}
printf("\n");
}
return 0;
}