PTA团体程序设计天梯赛 L3-014 周游世界 （Java）（满分不超时）
·
周游世界是件浪漫事，但规划旅行路线就不一定了…… 全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序，使得对任何给定的起点和终点，可以找出最顺畅的路线。所谓“最顺畅”，首先是指中途经停站最少；如果经停站一样多，则取需要换乘线路次数最少的路线。
输入格式：
输入在第一行给出一个正整数N（≤100），即联盟公司的数量。接下来有N行，第i行（i=1,⋯,N）描述了第i家公司所提供的线路。格式为：
M S[1] S[2] ⋯ S[M]
其中M（≤100）是经停站的数量，S[i]（i=1,⋯,M）是经停站的编号（由4位0-9的数字组成）。这里假设每条线路都是简单的一条可以双向运行的链路，并且输入保证是按照正确的经停顺序给出的 —— 也就是说，任意一对相邻的S[i]和S[i+1]（i=1,⋯,M−1）之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间，每个运营区间只承包给一家公司。环线是有可能存在的，但不会不经停任何中间站点就从出发地回到出发地。当然，不同公司的线路是可能在某些站点有交叉的，这些站点就是客户的换乘点，我们假设任意换乘点涉及的不同公司的线路都不超过5条。
在描述了联盟线路之后，题目将给出一个正整数K（≤10），随后K行，每行给出一位客户的需求，即始发地的编号和目的地的编号，中间以一空格分隔。
输出格式：
处理每一位客户的需求。如果没有现成的线路可以使其到达目的地，就在一行中输出“Sorry, no line is available.”；如果目的地可达，则首先在一行中输出最顺畅路线的经停站数量（始发地和目的地不包括在内），然后按下列格式给出旅行路线：
Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
......
其中Xi是线路承包公司的编号，Si是经停站的编号。但必须只输出始发地、换乘点和目的地，不能输出中间的经停站。题目保证满足要求的路线是唯一的。
输入样例：
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013
6666 2001
2004 3001
2222 6666
输出样例：
2
Go by the line of company #3 from 3011 to 3013.
10
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
6
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.
代码长度限制
16 KB
时间限制
200 ms
内存限制
64 MB
栈限制
8192 KB
import java.util.*;
import java.io.*;
/**
* L3-014 周游世界
* * [算法思路]
* 1. 建模：将车站视为节点(0000-9999)，区间视为边。
* - 使用静态邻接表 (head, to, nxt) 存储图，规避 ArrayList 的对象开销。
* - 线路存储：edgeLines[edgeIdx] 存储该物理区间所属的所有线路 ID。
* * 2. 搜索策略 (双重约束下的最短路)：
* - 第一优先级（经停最少）：先运行 BFS 计算起点到所有点的最短步数 minStopsArr[]。
* - 第二优先级（换乘最少）：在 BFS 步数约束下进行 DFS 深度优先搜索。
* * 3. 核心剪枝与优化 (针对 200ms 限制)：
* - 步数剪枝：DFS 时若 step > minStopsArr[u]，证明不是最短路径，直接回溯。
* - 记忆化剪枝：minTransAt[u] 记录到达 u 点的最少换乘。若当前换乘数已超过记录值，停止搜索。
* - 线路锁定：在 DFS 中实时携带 preLine。若当前边 [u, v] 包含 preLine，则强制不换乘，保持路径“顺畅”。
*/
public class Main {
// 静态邻接表，MAXV 为最大站点数，MAXE 为双向边最大可能数
static final int MAXV = 10000;
static final int MAXE = 40005;
static int[] head = new int[MAXV], to = new int[MAXE], nxt = new int[MAXE];
// edgeLines[i] 存储第 i 条边所属的所有公司线路编号 (题目说明换乘线不超过5条)
static int[][] edgeLines = new int[MAXE][6];
static int[] edgeLinesCnt = new int[MAXE];
static int edgeCnt = 0;
// 搜索状态记录
static int[] minStopsArr = new int[MAXV]; // 起点到各站的最短距离
static int[] minTransAt = new int[MAXV]; // 起点到各站的最少换乘数 (用于 DFS 剪枝)
static int minTransTotal, targetEnd;
// 路径存储
static int[] bestPath = new int[MAXV];
static int[] curPath = new int[MAXV];
static int bestPathLen;
public static void main(String[] args) throws IOException {
FastReader fr = new FastReader();
Arrays.fill(head, -1);
// 1. 读入线路信息并构图
int n = fr.nextInt();
for (int i = 1; i <= n; i++) {
int m = fr.nextInt();
int u = fr.nextInt();
for (int j = 1; j < m; j++) {
int v = fr.nextInt();
addEdge(u, v, i); // 添加无向边，并关联线路 i
addEdge(v, u, i);
u = v;
}
}
// 2. 处理 K 次查询
int k = fr.nextInt();
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
while (k-- > 0) {
int start = fr.nextInt();
targetEnd = fr.nextInt();
// 步数锁定：BFS 获取最短站数
bfs(start);
if (minStopsArr[targetEnd] == Integer.MAX_VALUE) {
out.println("Sorry, no line is available.");
continue;
}
// 换乘锁定：DFS 获取最小换乘路径
minTransTotal = Integer.MAX_VALUE;
Arrays.fill(minTransAt, Integer.MAX_VALUE);
curPath[0] = start;
dfs(start, 0, 0, -1, new boolean[MAXV]);
// 3. 输出结果
out.println(minStopsArr[targetEnd]);
printFormattedPath(out);
}
out.flush();
out.close();
}
/**
* 静态邻接表添加边
* 如果 u-v 之间已存在边，则在该边的线路列表中追加新的 lineID
*/
static void addEdge(int u, int v, int line) {
int e = -1;
for (int i = head[u]; i != -1; i = nxt[i]) {
if (to[i] == v) { e = i; break; }
}
if (e == -1) {
to[edgeCnt] = v;
nxt[edgeCnt] = head[u];
edgeLines[edgeCnt][edgeLinesCnt[edgeCnt]++] = line;
head[u] = edgeCnt++;
} else {
edgeLines[e][edgeLinesCnt[e]++] = line;
}
}
/**
* BFS 寻找经停站最少路径
* 结果存储在 minStopsArr 中，为 DFS 提供强力剪枝依据
*/
static void bfs(int start) {
Arrays.fill(minStopsArr, Integer.MAX_VALUE);
int[] q = new int[MAXV];
int l = 0, r = 0;
minStopsArr[start] = 0;
q[r++] = start;
while (l < r) {
int u = q[l++];
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (minStopsArr[v] == Integer.MAX_VALUE) {
minStopsArr[v] = minStopsArr[u] + 1;
q[r++] = v;
}
}
}
}
/**
* DFS 寻找换乘最少路径
* @param u 当前节点
* @param step 当前经停站数
* @param trans 当前换乘次数
* @param preLine 上一段路使用的线路ID
*/
static void dfs(int u, int step, int trans, int preLine, boolean[] vis) {
// [剪枝] 步数非最短 或 换乘数已劣于当前最优解
if (step > minStopsArr[targetEnd] || trans > minTransTotal) return;
// [记忆化剪枝] 若到达 u 时换乘数更多，则无需继续此分支
if (trans > minTransAt[u]) return;
minTransAt[u] = trans;
if (u == targetEnd) {
if (trans < minTransTotal) {
minTransTotal = trans;
bestPathLen = step + 1;
System.arraycopy(curPath, 0, bestPath, 0, bestPathLen);
}
return;
}
vis[u] = true;
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
// 仅搜索满足最短路性质的节点
if (!vis[v] && minStopsArr[v] == step + 1) {
curPath[step + 1] = v;
// 检查当前线路是否可以继续使用（避免换乘）
boolean canKeep = false;
if (preLine != -1) {
for (int k = 0; k < edgeLinesCnt[i]; k++) {
if (edgeLines[i][k] == preLine) { canKeep = true; break; }
}
}
if (canKeep) {
// 继续使用当前线路，换乘数不变
dfs(v, step + 1, trans, preLine, vis);
} else {
// 必须换乘：遍历该物理区间所属的所有线路
for (int k = 0; k < edgeLinesCnt[i]; k++) {
int newLine = edgeLines[i][k];
dfs(v, step + 1, (preLine == -1 ? 0 : trans + 1), newLine, vis);
}
}
}
}
vis[u] = false;
}
/**
* 格式化输出最终路径
* 仅在换乘点和终点触发 "Go by..." 打印
*/
static void printFormattedPath(PrintWriter out) {
int startNode = bestPath[0];
int preLine = -1;
for (int i = 0; i < bestPathLen - 1; i++) {
int u = bestPath[i], v = bestPath[i+1];
int e = -1;
for (int j = head[u]; j != -1; j = nxt[j]) if (to[j] == v) { e = j; break; }
boolean canKeep = false;
if (preLine != -1) {
for (int k = 0; k < edgeLinesCnt[e]; k++) if (edgeLines[e][k] == preLine) { canKeep = true; break; }
}
if (!canKeep) {
if (preLine != -1) {
out.printf("Go by the line of company #%d from %04d to %04d.\n", preLine, startNode, u);
}
// 切换到新线路
preLine = edgeLines[e][0];
startNode = u;
}
}
out.printf("Go by the line of company #%d from %04d to %04d.\n", preLine, startNode, bestPath[bestPathLen - 1]);
}
static class FastReader {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int nextInt() throws IOException {
while (st == null || !st.hasMoreElements()) {
String s = br.readLine();
if (s == null) return 0;
st = new StringTokenizer(s);
}
return Integer.parseInt(st.nextToken());
}
}
}
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
4
0- 0
已为社区贡献13条内容
所有评论(0)