输入格式: 输入第一行是三个正整数 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 的站点出发。 输出格式: 对于森森每个尝试的站点,输出一行若干个整数,表示能够到达的站点编号。站点编号从小到大排序。
时间: 2024-03-09 09:44:45 浏览: 54
我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k 第二行输入n个整数(c1 c2
这道题目可以用迪杰斯特拉算法来解决。具体步骤如下:
1. 构建图:读入每一条线路的信息,然后根据站点之间的距离构建图。
2. 进行迪杰斯特拉算法:以每个站点为起点,分别计算到其他站点的最短距离。
3. 输出结果:对于每个输入的起点站,输出它能够到达的所有站点。
下面是Java代码实现:
```java
import java.util.*;
public class Main {
static int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
Map<Integer, List<Edge>> graph = new HashMap<>();
for (int i = 0; i < m; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int d = scanner.nextInt();
addEdge(graph, x, y, d);
addEdge(graph, y, x, d);
}
int q = scanner.nextInt();
while (q-- > 0) {
int x = scanner.nextInt();
int[] dist = dijkstra(graph, n, x);
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (dist[i] != INF && i != x) {
list.add(i);
}
}
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
if (i < list.size() - 1) {
System.out.print(" ");
}
}
System.out.println();
}
}
static void addEdge(Map<Integer, List<Edge>> graph, int x, int y, int d) {
if (!graph.containsKey(x)) {
graph.put(x, new ArrayList<>());
}
graph.get(x).add(new Edge(y, d));
}
static int[] dijkstra(Map<Integer, List<Edge>> graph, int n, int s) {
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
dist[s] = 0;
PriorityQueue<Edge> queue = new PriorityQueue<>();
queue.offer(new Edge(s, 0));
while (!queue.isEmpty()) {
Edge edge = queue.poll();
int u = edge.u;
if (edge.d > dist[u]) {
continue;
}
for (Edge e : graph.get(u)) {
int v = e.u;
int w = e.d;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
queue.offer(new Edge(v, dist[v]));
}
}
}
return dist;
}
static class Edge implements Comparable<Edge> {
int u;
int d;
public Edge(int u, int d) {
this.u = u;
this.d = d;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(d, o.d);
}
}
}
```
其中,addEdge方法用于添加一条边;dijkstra方法用于求解最短路径;Edge类表示一条边,包括终点和距离。
阅读全文