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(){
//input
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;
}
//solve
for(int k = 1; k <= n; k++)//Floyd
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++){//从点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++){//更新点i能到达的最远点或者端点
if(G[i][j]==cost[2+G[i][j]/k] || i!=j&&ed[j]&&G[i][j]!=inf){
st[i].push_back(j);
}
}
/*此时其他的st还没有更新完
memset(vis,0,sizeof(vis));
vis[i] = 1;
dfs(i);
for(int j = 1; j <= n; j++)
if(vis[j])st[i].push_back(j);
sort(st[i].begin(), st[i].end());
st[i].erase(unique(st[i].begin(), st[i].end()), st[i].end());
*/
}
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;
}
