团体天梯 L3-022 地铁一日游（30 分)（思路求解）

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

真难受！这题目到底想说个啥？求大神解惑

十六分代码（T.T）:

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
struct Line {
	int visited = 0, last = 0;
	vector<int> road;
}line[201];
int graph[201][201];
const int MAX = 1000000001;
void search(int i, const int& vis) {
	for (auto &it : line[i].road) {
		if (line[it].visited != vis) {
			line[it].visited = vis;
			search(it, vis);
		}
	}
}
int main() {
	int n, m, k, dis, a, b, q, start;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			graph[i][j] = MAX;
	for (int i = 0; i < m; i++) {
		cin >> a;    //录入数据
		line[a].last = 1;
		do {
			cin >> dis >> b;
			if (graph[a][b] == 0 || graph[a][b] > dis) {
				graph[a][b] = graph[b][a] = dis;
			}
			a = b;
		} while (getchar() != '\n');
		line[a].last = 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&&graph[i][j] > graph[i][k] + graph[k][j])
					graph[i][j] = graph[i][k] + graph[k][j];
	for (int i = 1; i <= n; i++) {
		map<int, int> mp;  
		for (int j = 1; j <= n; j++)   //寻找每个费用的最远距离
			if (graph[i][j] != MAX && graph[i][j] > mp[2+graph[i][j]/k])
				mp[2+graph[i][j] / k] = graph[i][j];
		for (int j = 1; j <= n; j++)   //录入数据，构建邻接表
			if (graph[i][j] == mp[2+graph[i][j] / k]||(i!=j&&line[j].last))
				line[i].road.push_back(j);
	}
	cin >> q;
	int flag;
	for (int i = 1; i <= q; i++) {
		cin >> start;
		line[start].visited = i;
		flag = 0;
		search(start, i);  //搜索
		for (int j = 1; j <= n; j++) 
			if (line[j].visited == i) {
				cout <<(flag?" ":"")<< j ;
				flag = 1;
			}
		cout << endl;
	}
	return 0;
}

团体天梯 L3-022 地铁一日游 （30 分)（思路求解）