problem
L3-022 地铁一日游 (30分) 森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！
魔都地铁的计价规则是：起步价 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 ≤ 106)，加 1 元车费。
接下来 M 行，每行由以下格式组成：
<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>
其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。
注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。
再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。
最后有 Q 行，每行一个正整数 Xi，表示森森尝试从编号为 Xi 的站点出发。
输出格式: 对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。
输入样例: 6 2 6 1 6 2 4 3 1 4 5 6 2 6 6 4 2 3 4 5 输出样例: 1 2 4 5 6 1 2 3 4 5 6 1 2 4 5 6 1 2 4 5 6
n个点，m条线路（含距离）串起一张图。每k公里（最短距离）增加1元钱，从一点出发，相同费用时距离最远的出站，或者端点出站。q个询问，从x出发能到达的站点的编号。
solution
开邻接矩阵维护任意两点间最短距离，输入时更新，跑一遍floyd更新。扫一遍更新从点i出发会出站的点（相同费用最远点或端点），其中前者用map维护相同费用的点遍历一遍其他能到达的点来更新。因为从x出发可能会到达其他线路的端点，所以要跑一边dfs把这些点都加上去。
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 210;
const int inf
= 1e9+10;
int G
[maxn
][maxn
];
vector
<int>st
[maxn
]; int ed
[maxn
], vis
[maxn
];
void dfs(int u
){
for(int i
= 0; i
< st
[u
].size(); i
++){
int v
= st
[u
][i
];
if(!vis
[v
]){
vis
[v
] = 1;
dfs(v
);
}
}
}
int main(){
int n
, m
, k
; cin
>>n
>>m
>>k
;
for(int i
= 1; i
<= n
; i
++)
for(int j
= 1; j
<= n
; j
++)
G
[i
][j
] = inf
;
for(int i
= 1; i
<= m
; i
++){
int a
, b
, dis
;
cin
>>a
; ed
[a
] = 1;
while(cin
>>dis
>>b
){
G
[a
][b
] = min(G
[a
][b
], dis
);
G
[b
][a
] = min(G
[b
][a
], dis
);
a
= b
;
if(getchar()=='\n')break;
}
ed
[a
] = 1;
}
for(int k
= 1; k
<= n
; k
++)
for(int i
= 1; i
<= n
; i
++)
for(int j
= 1; j
<= n
; j
++)
if(i
!=j
)G
[i
][j
] = min(G
[i
][j
],G
[i
][k
]+G
[k
][j
]);
for(int i
= 1; i
<= n
; i
++){
map
<int,int>cost
;
for(int j
= 1; j
<= n
; j
++){
if(G
[i
][j
]==inf
)continue;
cost
[2+G
[i
][j
]/k
] = max(cost
[2+G
[i
][j
]/k
],G
[i
][j
]);
}
for(int j
= 1; j
<= n
; j
++){
if(G
[i
][j
]==cost
[2+G
[i
][j
]/k
] || i
!=j
&&ed
[j
]&&G
[i
][j
]!=inf
){
st
[i
].push_back(j
);
}
}
}
int q
; cin
>>q
;
for(int i
= 1; i
<= q
; i
++){
int x
; cin
>>x
;
memset(vis
,0,sizeof(vis
));
vis
[x
] = 1;
dfs(x
);
for(int j
= 1; j
<= n
; j
++)
if(vis
[j
])st
[x
].push_back(j
);
sort(st
[x
].begin(), st
[x
].end());
st
[x
].erase(unique(st
[x
].begin(), st
[x
].end()), st
[x
].end());
for(int j
= 0; j
< st
[x
].size(); j
++){
if(j
!=0)cout
<<" ";
cout
<<st
[x
][j
];
}
cout
<<"\n";
}
return 0;
}
