输入第一行是三个正整数 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给出完整c++代码
时间: 2024-03-10 15:49:24 浏览: 32
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 210, M = 15010;
const int INF = 0x3f3f3f3f;
int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int get(int x) {
int res = x / k;
if (x % k) res ++;
return res;
}
void dijkstra(int start) {
memset(dist, 0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
dist[start] = 0;
cnt[start] = 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, start});
while (q.size()) {
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
cnt[j] = cnt[ver] + 1;
q.push({dist[j], j});
} else if (dist[j] == distance + w[i]) {
cnt[j] = max(cnt[j], cnt[ver] + 1);
}
}
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m >> k;
for (int i = 0; i < m; i ++) {
int cnt;
cin >> cnt;
int first;
cin >> first;
for (int j = 1; j < cnt; j ++) {
int second, distance;
cin >> second >> distance;
add(first, second, distance);
add(second, first, distance);
first = second;
}
}
int q;
cin >> q;
while (q --) {
int start;
cin >> start;
dijkstra(start);
int res = 0;
for (int i = 1; i <= n; i ++) {
if (cnt[i] <= 1) continue;
if (get(dist[i]) > 1) continue;
res ++;
cout << i << " ";
}
if (!res) puts("0");
else puts("");
for (int i = 1; i <= n; i ++) {
if (dist[i] == INF) dist[i] = -1;
}
}
return 0;
}
```