网址大全免费网站,榆林市网站seo,如果用别人公司信息做网站,重庆的推广网站森森喜欢坐地铁。这个假期#xff0c;他终于来到了传说中的地铁之城——魔都#xff0c;打算好好过一把坐地铁的瘾#xff01;
魔都地铁的计价规则是#xff1a;起步价 2 元#xff0c;出发站与到达站的最短距离#xff08;即计费距离#xff09;每 K 公里增加 1 元车费…
森森喜欢坐地铁。这个假期他终于来到了传说中的地铁之城——魔都打算好好过一把坐地铁的瘾
魔都地铁的计价规则是起步价 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
代码实现
#include algorithm
#include cstdio
#include map
#include queue
using namespace std;
const int maxn 205;
const int INF 0x3f3f3f3f;
int d[maxn][maxn];
int terminal[maxn], vis[maxn][maxn];
mapint, int been[maxn];
int n, m, k;
int line[10000];int main() {
#ifdef LOCALfreopen(E:\\Cpp\\1.in, r, stdin);
#endifscanf(%d%d%d, n, m, k);for (int i 1; i n; i)for (int j 1; j n; j)d[i][j] (i j) ? 0 : INF;int u, v, len;int fare;char ch;while (m--) {int len 0;while (scanf(%d, u)) {line[len] u;ch getchar();if (ch \n) {terminal[line[0]] terminal[line[len - 1]] 1;for (int i 0; i ! len - 1; i 2) {u line[i], v line[i 2];d[v][u] d[u][v] min(d[u][v], line[i 1]);}break;}}}for (int k 1; k n; k) {for (int i 1; i n; i)for (int j 1; j n; j)d[i][j] min(d[i][j], d[i][k] d[k][j]);}for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j || d[i][j] INF)continue;fare 2 d[i][j] / k;if (!been[i].count(fare) || been[i][fare] d[i][j])been[i][fare] d[i][j];}}int t, cur, first;queueint Q;scanf(%d, t);while (t--) {first 1;scanf(%d, u);vis[u][u] 1;Q.push(u);while (!Q.empty()) {cur Q.front();Q.pop();for (int i 1; i n; i) {if (vis[u][i] || d[cur][i] INF)continue;if (terminal[i]) {Q.push(i);vis[u][i] 1;} else {fare 2 d[cur][i] / k;if (d[cur][i] been[cur][fare]) {Q.push(i);vis[u][i] 1;}}}}for (int i 1; i n; i) {if (vis[u][i]) {if (first) {printf(%d, i);first 0;} elseprintf( %d, i);}}printf(\n);}return 0;
}
