题目链接
题目描述
在一个由 个星系和
条“跃迁航线”组成的网络中，计算从一个起始星系到一个目标星系所需的最少航线换乘次数。
- 每条航线连接多个星系。
- 如果两条航线都经过同一个星系，探险家就可以在该星系进行一次“航线换乘”。
- 如果起始和目标星系在同一条航线上，则无需换乘。
解题思路
这是一个最短路径问题，但其成本单位不是距离或边的数量，而是“换乘次数”。直接在星系图上求解很困难。关键在于将“航线”本身也模型化为图的一部分，从而将“换乘”这个动作转化为路径成本。
1. 核心思想：构建混合图
我们将构建一个包含两种类型节点的图：
- 星系节点：共
个，代表物理位置。
- 航线节点：共
个，作为虚拟节点，代表每条跃迁航线。
2. 图的构建与权重设计
为了计算换乘次数，我们设计如下的边和权重：
-
节点编号：
- 星系
- 航线
- 星系
-
边的建立：对于第
条航线（对应航线节点
）上的每一个星系
：
- 建立一条从 星系节点
- 这代表在一个星系“登上”某条航线，这个动作本身不产生换乘成本。
- 建立一条从 航线节点
- 这代表使用某条航线旅行并“到达”一个星系。我们将成本（1）计在这里，代表使用了一条航线。
- 建立一条从 星系节点
3. 路径与换乘次数的转换
- 路径权重：在这个图中，从起始星系
到目标星系
的一条路径，其总权重等于旅途中所使用的航线数量。
- 例如，路径
S -> 航线A -> G -> 航线B -> T的权重为weight(S->A) + weight(A->G) + weight(G->B) + weight(B->T) = 0 + 1 + 0 + 1 = 2。这表示使用了2条航线。
- 例如，路径
- 换乘次数：题目要求的是最少换乘次数。如果我们最少需要使用
条航线来到达目的地，那么换乘次数就是
（第一条航线不算换乘）。
- 因此，最终答案是
(S到T的最短路径权重) - 1。 - 如果
S -> 航线A -> T，权重为1，换乘次数为1-1=0，符合题意。
- 因此，最终答案是
4. 算法选择：0-1 BFS
由于图中边的权重只有 0 和 1 两种，这是 0-1 BFS 的经典应用场景。它使用一个双端队列 (deque) 来实现，时间复杂度与标准 BFS 相同，为 ，比需要优先队列的 Dijkstra 算法更高效。
- 算法流程：
- 为每个查询
(S, T)初始化距离数组dist。 - 将源点
S放入 deque，dist[S]=0。 - 从 deque 头部取出一个节点
u。 - 遍历
u的邻居v：- 如果找到了更短的路径 (
dist[u] + weight(u,v) < dist[v])：- 更新
dist[v]。 - 如果
weight(u,v)是 0，将v加入 deque 的头部。 - 如果
weight(u,v)是 1，将v加入 deque 的尾部。
- 更新
- 如果找到了更短的路径 (
- 为每个查询
- 最终结果：
- BFS 结束后，若
dist[T]为无穷大，则不可达，输出-1。 - 否则，输出
dist[T] - 1。
- BFS 结束后，若
代码
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <sstream>
using namespace std;
const int INF = 1e9;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n_galaxies, m_routes, q_queries;
cin >> n_galaxies >> m_routes >> q_queries;
int total_nodes = n_galaxies + m_routes;
vector<vector<pair<int, int>>> adj(total_nodes);
string line;
getline(cin, line); // Consume the rest of the first line
for (int i = 0; i < m_routes; ++i) {
getline(cin, line);
stringstream ss(line);
int k, galaxy;
ss >> k;
int route_node = n_galaxies + i;
for (int j = 0; j < k; ++j) {
ss >> galaxy;
// 星系 -> 航线, weight 0
adj[galaxy].push_back({route_node, 0});
// 航线 -> 星系, weight 1
adj[route_node].push_back({galaxy, 1});
}
}
for (int i = 0; i < q_queries; ++i) {
int start_galaxy, end_galaxy;
cin >> start_galaxy >> end_galaxy;
if (start_galaxy == end_galaxy) {
cout << 0 << "\n";
continue;
}
vector<int> dist(total_nodes, INF);
deque<int> dq;
dist[start_galaxy] = 0;
dq.push_front(start_galaxy);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
if (u == end_galaxy) break;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
if (weight == 0) {
dq.push_front(v);
} else {
dq.push_back(v);
}
}
}
}
if (dist[end_galaxy] == INF) {
cout << -1 << "\n";
} else {
cout << dist[end_galaxy] - 1 << "\n";
}
}
return 0;
}
import java.util.*;
class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nGalaxies = sc.nextInt();
int mRoutes = sc.nextInt();
int qQueries = sc.nextInt();
int totalNodes = nGalaxies + mRoutes;
List<List<Edge>> adj = new ArrayList<>();
for (int i = 0; i < totalNodes; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < mRoutes; i++) {
int k = sc.nextInt();
int routeNode = nGalaxies + i; // 航线节点的编号
for (int j = 0; j < k; j++) {
int galaxy = sc.nextInt();
// 星系 -> 航线, 权重为 0
adj.get(galaxy).add(new Edge(routeNode, 0));
// 航线 -> 星系, 权重为 1
adj.get(routeNode).add(new Edge(galaxy, 1));
}
}
for (int i = 0; i < qQueries; i++) {
int startGalaxy = sc.nextInt();
int endGalaxy = sc.nextInt();
if (startGalaxy == endGalaxy) {
System.out.println(0);
continue;
}
int[] dist = new int[totalNodes];
Arrays.fill(dist, Integer.MAX_VALUE);
Deque<Integer> dq = new ArrayDeque<>();
// 0-1 BFS 初始化
dist[startGalaxy] = 0;
dq.addFirst(startGalaxy);
while (!dq.isEmpty()) {
int u = dq.pollFirst();
if (u == endGalaxy) break;
for (Edge edge : adj.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
// 权重为 0 的边，加到队首
if (weight == 0) {
dq.addFirst(v);
} else {
// 权重为 1 的边，加到队尾
dq.addLast(v);
}
}
}
}
if (dist[endGalaxy] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
// 路径权重等于航线数，换乘数 = 航线数 - 1
System.out.println(dist[endGalaxy] - 1);
}
}
}
}
import sys
import collections
def main():
# 读取第一行：星系数量，航线数量，查询数量
n_galaxies, m_routes, q_queries = map(int, input().split())
total_nodes = n_galaxies + m_routes
adj = collections.defaultdict(list)
# 构建图
for i in range(m_routes):
line = list(map(int, input().split()))
galaxies = line[1:]
route_node = n_galaxies + i # 航线节点的编号
for galaxy in galaxies:
# 星系 -> 航线, 权重为 0
adj[galaxy].append((route_node, 0))
# 航线 -> 星系, 权重为 1
adj[route_node].append((galaxy, 1))
# 处理查询
for _ in range(q_queries):
start_galaxy, end_galaxy = map(int, input().split())
if start_galaxy == end_galaxy:
print(0)
continue
dist = {i: float('inf') for i in range(total_nodes)}
dq = collections.deque()
# 0-1 BFS 初始化
dist[start_galaxy] = 0
dq.appendleft(start_galaxy)
result = -1
while dq:
u = dq.popleft()
if u == end_galaxy:
result = dist[u]
break
for v, weight in adj[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# 权重为 0 的边，加到队首
if weight == 0:
dq.appendleft(v)
# 权重为 1 的边，加到队尾
else:
dq.append(v)
if result == -1 or result == float('inf'):
print(-1)
else:
# 路径权重等于航线数，换乘数 = 航线数 - 1
print(result - 1)
if __name__ == "__main__":
main()
算法及复杂度
- 算法: 图论建模, 0-1 广度优先搜索 (BFS)
- 时间复杂度:
，其中
是所有航线包含的星系总数。
- 建图的时间复杂度为
。
- 每个查询执行一次 0-1 BFS，其复杂度为
，其中
是节点数，
是边数。
- 总时间复杂度由建图和
次查询构成。
- 建图的时间复杂度为
- 空间复杂度:
，用于存储图的邻接表以及 BFS 所需的距离数组和队列。
京公网安备 11010502036488号