Leetcode+Java+图论+最短路径问题

YSRM

869人浏览 · 2025-10-21 16:43:48

YSRM · 2025-10-21 16:43:48 发布

47.参加科学大会

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

输入描述

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

输出描述

输出一个整数，代表小明从起点到终点所花费的最小时间。

输入示例
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
输出示例
12
提示信息

能够到达的情况：

如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。

不能到达的情况：

如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

数据范围：

1 <= N <= 500;
1 <= M <= 5000;

原理

核心：贪心选择 + 松弛操作+邻接矩阵

text

1. 初始化：minDist[start]=0，其他=∞
2. 优先队列存储(节点,距离)对
3. 循环：
   a. 取出当前最短距离节点cur
   b. 用cur松弛所有邻接节点
4. 无法到达 → minDist[end]=∞ → 输出-1

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 节点数
        int M = scanner.nextInt();  // 边数
        
        // 邻接矩阵：grid[s][t] = 从s到t的权重
        int[][] grid = new int[N + 1][N + 1];
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        
        // 初始化矩阵为∞
        for (int i = 0; i <= N; i++) Arrays.fill(grid[i], Integer.MAX_VALUE);
        
        int start = 1, end = N;
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid[s][t] = val;  // 单向边 s→t
        }
        
        boolean[] flag = new boolean[N + 1];  // 已访问标记
        minDist[start] = 0;
        
        // Dijkstra：N次迭代
        for (int i = 1; i <= N; i++) {
            // 找未访问节点中minDist最小的cur
            int min_val = Integer.MAX_VALUE, cur = 1;
            for (int j = 1; j <= N; j++) {
                if (!flag[j] && minDist[j] < min_val) {
                    min_val = minDist[j];
                    cur = j;
                }
            }
            flag[cur] = true;  // 加入最短路径树
            
            // 松弛操作：更新cur所有邻接节点
            for (int j = 1; j <= N; j++) {
                if (!flag[j] && grid[cur][j] != Integer.MAX_VALUE && 
                    minDist[cur] + grid[cur][j] < minDist[j]) {
                    minDist[j] = minDist[cur] + grid[cur][j];
                }
            }
        }
        
        // 输出结果
        System.out.print(minDist[end] == Integer.MAX_VALUE ? -1 : minDist[end]);
    }
}

原理

核心：贪心选择 + 松弛操作+优先队列

text

1. 初始化：minDist[start]=0，其他=∞
2. 优先队列存储(节点,距离)对
3. 循环：
   a. 取出当前最短距离节点cur
   b. 用cur松弛所有邻接节点
4. 无法到达 → minDist[end]=∞ → 输出-1

代码

import java.util.*;

class Edge { int to, val; Edge(int to, int val) { this.to = to; this.val = val; } }
class Pair { int target, val; Pair(int u, int v) { this.target = u; this.val = v; } }

class MyComparison implements Comparator<Pair> {
    public int compare(Pair a, Pair b) { return Integer.compare(a.val, b.val); }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(), M = scanner.nextInt();
        
        // 邻接表
        List<List<Edge>> grid = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) grid.add(new ArrayList<>());
        
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        int start = 1, end = N;
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid.get(s).add(new Edge(t, val));
        }
        
        minDist[start] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyComparison());
        pq.add(new Pair(start, 0));
        boolean[] flag = new boolean[N + 1];
        
        // Dijkstra：优先队列优化
        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            if (flag[cur.target]) continue;  // 过期节点跳过
            flag[cur.target] = true;
            
            // 松弛操作
            for (Edge edge : grid.get(cur.target)) {
                if (!flag[edge.to] && minDist[cur.target] + edge.val < minDist[edge.to]) {
                    minDist[edge.to] = minDist[cur.target] + edge.val;
                    pq.add(new Pair(edge.to, minDist[edge.to]));
                }
            }
        }
        
        System.out.print(minDist[end] == Integer.MAX_VALUE ? -1 : minDist[end]);
    }
}

94.城市间货物运输I

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n，请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

输入示例
6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5
输出示例
1
提示信息

示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 "unconnected"。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

原理

Bellman-Ford算法

核心：全局松弛 + 负权支持

text

1. 初始化：minDist[start]=0，其他=∞
2. N-1轮松弛：
   遍历所有边(s→t,v)：
   if minDist[s] + v < minDist[t]：
       minDist[t] = minDist[s] + v
3. 第N轮检测负环（本题保证无负环）
4. 无法到达 → "unconnected"

代码

import java.util.*;

class Edge {
    int to, val;
    Edge(int to, int val) { this.to = to; this.val = val; }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 城市数
        int M = scanner.nextInt();  // 道路数
        
        // 邻接表：grid[s] = 从s出发的所有边
        List<List<Edge>> grid = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) grid.add(new ArrayList<>());
        
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        int start = 1, end = N;
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid.get(s).add(new Edge(t, val));  // s→t，权值v
        }
        
        minDist[start] = 0;
        
        // Bellman-Ford：最多N-1轮松弛
        boolean flag = true;
        for (int i = 0; i < N - 1; i++) {
            flag = true;  // 标记本轮是否有更新
            for (int j = 0; j <= N; j++) {  // 遍历所有节点
                int s = j;
                for (Edge edge : grid.get(s)) {  // 遍历s的所有出边
                    int t = edge.to;
                    int val = edge.val;
                    // 松弛操作：如果能更新就更新
                    if (minDist[s] != Integer.MAX_VALUE && 
                        minDist[s] + val < minDist[t]) {
                        minDist[t] = minDist[s] + val;
                        flag = false;  // 有更新，继续松弛
                    }
                }
            }
            if (flag) break;  // 无更新，提前结束
        }
        
        // 输出结果
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.print("unconnected");
        } else {
            System.out.print(minDist[end]);
        }
    }
}

原理

核心：松弛优先 + 始终入队

text

1. 初始化：minDist[start]=0，其他=∞
2. 队列初始：queue=[start]
3. 循环：
   a. 取出cur
   b. 对cur所有邻接(t,v)：
      if minDist[cur]+v < minDist[t]：
         minDist[t] = minDist[cur]+v
         queue.add(t)  // 始终入队！
4. 无法到达 → "unconnected"

代码

import java.util.*;

class Edge {
    int to, val;
    Edge(int to, int val) { this.to = to; this.val = val; }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(), M = scanner.nextInt();
        
        // 邻接表
        List<List<Edge>> grid = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) grid.add(new ArrayList<>());
        
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        int start = 1, end = N;
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid.get(s).add(new Edge(t, val));
        }
        
        minDist[start] = 0;
        
        // 队列版Dijkstra（支持负权！）
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            
            // 松弛操作
            for (Edge edge : grid.get(cur)) {
                int tar = edge.to;
                int val = edge.val;
                
                // 如果能更新距离
                if (minDist[tar] == Integer.MAX_VALUE || 
                    minDist[cur] + val < minDist[tar]) {
                    minDist[tar] = minDist[cur] + val;
                    
                    // 关键：始终入队（支持负权更新）
                    if (!queue.contains(tar)) {
                        queue.add(tar);
                    }
                }
            }
        }
        
        // 输出结果
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.print("unconnected");
        } else {
            System.out.print(minDist[end]);
        }
    }
}

95.城市间货物运输II

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

输出描述

如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 "circle"。如果从城市 1 无法到达城市 n，则输出 "unconnected"。

输入示例
4 4
1 2 -1
2 3 1
3 1 -1 
3 4 1
输出示例
circle
提示信息

路径中存在负权回路，从 1 -> 2 -> 3 -> 1，总权值为 -1，理论上货物运输商可以在该回路无限循环赚取政府补贴，所以输出 "circle" 表示已经检测出了该种情况。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

原理

Bellman-Ford + 负权回路检测

核心：N-1轮松弛 + 第N轮检测

text

1. 初始化：minDist[1]=0，其他=∞
2. N-1轮松弛：计算最短路径
3. 第N轮松弛：
   - 如果还能更新 → 存在负权回路 → "circle"
   - 否则 → 无负环
4. 判断连通性：
   - minDist[n]=∞ → "unconnected"
   - 否则 → 输出minDist[n]

代码

import java.util.*;

class Edge {
    int to, val;
    Edge(int to, int val) { this.to = to; this.val = val; }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 城市数
        int M = scanner.nextInt();  // 道路数
        
        // 邻接表：grid[s] = 从s出发的所有边
        List<List<Edge>> grid = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) grid.add(new ArrayList<>());
        
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        int start = 1, end = N;
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid.get(s).add(new Edge(t, val));  // s→t，权值v
        }
        
        minDist[start] = 0;
        
        // Bellman-Ford：N-1轮松弛（计算最短路径）
        boolean flag = true;
        for (int i = 0; i < N - 1; i++) {
            flag = true;  // 本轮是否有更新
            for (int j = 0; j <= N; j++) {
                int s = j;
                for (Edge edge : grid.get(s)) {
                    int t = edge.to;
                    int val = edge.val;
                    // 松弛操作
                    if (minDist[s] != Integer.MAX_VALUE && 
                        minDist[s] + val < minDist[t]) {
                        minDist[t] = minDist[s] + val;
                        flag = false;  // 有更新
                    }
                }
            }
            if (flag) break;  // 无更新，提前结束
        }
        
        // 第N轮：检测负权回路
        flag = true;
        for (int j = 0; j <= N; j++) {
            int s = j;
            for (Edge edge : grid.get(s)) {
                int t = edge.to;
                int val = edge.val;
                if (minDist[s] != Integer.MAX_VALUE && 
                    minDist[s] + val < minDist[t]) {
                    flag = false;  // 第N轮仍有更新 → 负权回路！
                    break;
                }
            }
            if (!flag) break;
        }
        
        // 输出结果
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.print("unconnected");  // 无法到达
        } else if (!flag) {
            System.out.print("circle");       // 有负权回路
        } else {
            System.out.print(minDist[end]);   // 正常最短路径
        }
    }
}

96.城市间货物运输III

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为城市编号，从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数，表示从城市 src 到城市 dst 的最低运输成本，如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径，则输出 "unreachable"，表示不存在符合条件的运输方案。

输入示例
6 7
1 2 1
2 4 -3
2 5 2
1 3 5
3 5 1
4 6 4
5 6 -2
2 6 1
输出示例
0
提示信息

从 2 -> 5 -> 6 中转一站，运输成本为 0。

1 <= n <= 1000；

1 <= m <= 10000;

-100 <= v <= 100;

原理

限制版Bellman-Ford

核心：K轮松弛（K=num+1）

text

1. 初始化：minDist[start]=0，其他=∞
2. num+1轮松弛：
   - 第i轮：最多经过i个中间城市
   - 使用上一轮距离更新本轮（防止连锁更新）
3. 无法到达 → "unreachable"

路径长度限制

text

- num=0：仅直达边 start→end
- num=1：最多1个中间城市，路径≤2条边
- num=k：最多k个中间城市，路径≤k+1条边

代码

import java.util.*;

class Edge {
    int to, val;
    Edge(int to, int val) { this.to = to; this.val = val; }
}

public class Main {
    public static main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 城市数
        int M = scanner.nextInt();  // 道路数
        
        // 邻接表：grid[s] = 从s出发的所有边
        List<List<Edge>> grid = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) grid.add(new ArrayList<>());
        
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        
        // 构建有向图
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid.get(s).add(new Edge(t, val));  // s→t，权值v
        }
        
        int start = scanner.nextInt();  // 起点
        int end = scanner.nextInt();    // 终点
        int num = scanner.nextInt();    // 最大经过城市数（路径长度限制）
        
        minDist[start] = 0;
        
        // 限制版Bellman-Ford：最多num+1轮松弛
        boolean flag = true;
        for (int i = 0; i <= num; i++) {  // i=0是起点，i=1到num是中间城市
            int[] minDist_copy = Arrays.copyOf(minDist, minDist.length);  // 复制当前距离
            flag = true;
            
            // 遍历所有边进行松弛
            for (int j = 0; j <= N; j++) {
                int s = j;
                for (Edge edge : grid.get(s)) {
                    int t = edge.to;
                    int val = edge.val;
                    // 使用上一轮距离更新本轮
                    if (minDist_copy[s] != Integer.MAX_VALUE && 
                        minDist_copy[s] + val < minDist[t]) {
                        minDist[t] = minDist_copy[s] + val;
                        flag = false;  // 有更新
                    }
                }
            }
            if (flag) break;  // 无更新，提前结束
        }
        
        // 输出结果
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.print("unreachable");
        } else {
            System.out.print(minDist[end]);
        }
    }
}

97.小明逛公园

题目描述

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。请你帮助小明计算出每个观景计划的最短路径长度。

输入描述

第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。

接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。

接下里的一行包含一个整数 Q，表示观景计划的数量。

接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。

输出描述

对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。

输入示例
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
输出示例
4
-1
提示信息

从 2 到 3 的路径长度为 4，3 到 4 之间并没有道路。

1 <= N, M, Q <= 1000.

1 <= w <= 10000.

原理

Floyd-Warshall算法

核心：动态规划 + 中间节点递增

text

状态：dp[i][j][k] = 从i到j经过中间节点{1,2,...,k}的最短路径

转移：
dp[i][j][k] = min(
    dp[i][j][k-1],                    // 不经过k
    dp[i][k][k-1] + dp[k][j][k-1]     // 经过k
)

初始：dp[i][j][0] = 直接边权，无边=∞
最终：dp[i][j][N] = 所有点对最短路径

执行流程

text

1. 初始化：grid[i][j][0] = 直接边权
2. 递推：
   k=1：考虑中间节点1的所有路径
   k=2：考虑中间节点{1,2}的所有路径
   ...
   k=N：考虑所有中间节点
3. 查询：grid[start][end][N]

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 景点数
        int M = scanner.nextInt();  // 道路数
        
        // 三维数组：grid[i][j][k] = 从i到j经过中间节点1..k的最短路径
        int[][][] grid = new int[N + 1][N + 1][N + 1];
        
        // 初始化：所有距离设为∞(10005)
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                Arrays.fill(grid[i][j], 10005);
            }
        }
        
        // 构建无向图：grid[u][v][0] = 直接边权
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt(), val = scanner.nextInt();
            grid[s][t][0] = val;  // s→t
            grid[t][s][0] = val;  // t→s（无向图）
        }
        
        // Floyd-Warshall算法：计算所有点对最短路径
        for (int k = 1; k <= N; k++) {  // 中间节点k
            for (int i = 1; i <= N; i++) {  // 起点i
                for (int j = 1; j <= N; j++) {  // 终点j
                    // 状态转移：grid[i][j][k] = min(不经k, 经k)
                    grid[i][j][k] = Math.min(
                        grid[i][k][k - 1] + grid[k][j][k - 1],  // 经k
                        grid[i][j][k - 1]                       // 不经k
                    );
                }
            }
        }
        
        int Q = scanner.nextInt();  // 查询数
        
        // 存储所有查询结果
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < Q; i++) {
            int s = scanner.nextInt(), t = scanner.nextInt();
            // grid[s][t][N] = 最终最短路径
            if (grid[s][t][N] == 10005) {
                queue.add(-1);  // 无法到达
            } else {
                queue.add(grid[s][t][N]);
            }
        }
        
        // 输出结果（每行一个）
        boolean flag = true;
        while (!queue.isEmpty()) {
            int result = queue.poll();
            if (!flag) {
                System.out.println();  // 换行
            }
            System.out.print(result);
            flag = false;
        }
    }
}

127.骑士的攻击

题目描述

在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

输入描述

第一行包含一个整数 n，表示测试用例的数量，1 <= n <= 100。

接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述

输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。

输入示例
6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6
输出示例
2
4
6
5
1
0
提示信息

骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。

原理

A*搜索算法

核心：最优优先队列 + 启发函数

text
f(n) = g(n) + h(n)
- g(n)：从起点到n的实际步数
- h(n)：从n到终点的估计步数（启发函数）
- f(n)：总估计值，按f升序搜索
骑士移动规则

text
8种可能移动：日字形
(-2,-1), (-2,1), (-1,-2), (-1,2), 
 (1,-2),  (1,2),  (2,-1),  (2,1)
启发函数

java
h = (x-b1)² + (y-b2)²  // 欧氏距离平方
性质：可接受启发，保证最优解

代码

import java.util.*;

public class Main {
    // moves[x][y]：到达(x,y)的最短步数
    static int[][] moves = new int[1001][1001];
    
    // 骑士8种移动方向：(dx,dy)
    static int[] dir = {-2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2};
    
    // 骑士节点类（A*算法）
    static class knight {
        int x, y, g, h, f;  // 当前坐标、已走步数、启发值、总估计值
        
        public knight(int x, int y, int g, int h, int f) {
            this.x = x; this.y = y; this.g = g; this.h = h; this.f = f;
        }
    }
    
    // 启发函数：曼哈顿距离（实际用欧氏距离）
    public static int Heuristic(knight start, int b1, int b2) {
        return (start.x - b1) * (start.x - b1) + (start.y - b2) * (start.y - b2);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 测试用例数
        
        // 优先队列：按f值升序（A*算法）
        PriorityQueue<knight> queue = new PriorityQueue<>((a, b) -> Integer.compare(a.f, b.f));
        
        for (int i = 0; i < n; i++) {
            int a1 = scanner.nextInt(), a2 = scanner.nextInt();  // 起点
            int b1 = scanner.nextInt(), b2 = scanner.nextInt();  // 终点
            
            // 初始化moves数组
            for (int j = 0; j <= 1000; j++) {
                Arrays.fill(moves[j], 0);
            }
            
            // 起始节点
            knight start = new knight(a1, a2, 0, 0, 0);
            start.h = Heuristic(start, b1, b2);
            start.f = start.h + start.g;
            
            queue.add(start);
            moves[a1][a2] = 0;  // 起点步数=0
            
            knight cur, next = new knight(0, 0, 0, 0, 0);
            boolean found = false;
            
            // A*搜索
            while (!queue.isEmpty() && !found) {
                cur = queue.poll();
                
                // 到达终点
                if (cur.x == b1 && cur.y == b2) {
                    if (i != 0) System.out.println();  // 换行（除第一行）
                    System.out.print(moves[b1][b2]);
                    found = true;
                    break;
                }
                
                // 尝试8种移动
                for (int j = 0; j < 8; j++) {
                    next.x = cur.x + dir[2 * j];     // dx
                    next.y = cur.y + dir[2 * j + 1]; // dy
                    
                    // 边界检查
                    if (next.x < 1 || next.y < 1 || next.x > 1000 || next.y > 1000) {
                        continue;
                    }
                    
                    // 未访问且在棋盘内
                    if (moves[next.x][next.y] == 0) {
                        moves[next.x][next.y] = moves[cur.x][cur.y] + 1;  // 步数+1
                        next.g = cur.g + 1;  // 实际步数
                        next.h = Heuristic(next, b1, b2);
                        next.f = next.g + next.h;
                        queue.add(new knight(next.x, next.y, next.g, next.h, next.f));
                    }
                }
            }
            queue.clear();
        }
        scanner.close();
    }
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

推荐几个牛逼的AI Agent项目

使用技术：JDK21、SpringBoot3.5.3、JPA、Redis、布隆过滤器、Sentinel、Nacos、Redisson、shardingsphere、HikariCP、guava、Prometheus、AlertManager、Grafana、ELK等。通过这个项目，可以学到很多高并发、流量评估、分库分表、多级缓存、多级布隆过滤器、限流、熔断、多线程、监控、报警、数据扩容、集群、广播

AI Agent技术社区

MCP协议开发实战：从零搭建AI Agent工具链

AI Agent技术社区

AI Agent 面试题 625：如何评估和优化RAG系统的检索延迟？

检索排序优化是 AI Agent 技术体系中的重要组成部分。简单来说，它涉及到 Agent 如何在 RAG与知识库层面实现智能化的行为和决策。在实际应用中，检索排序优化的核心目标是让 Agent 能够更加高效、准确地完成特定任务。这需要我们深入理解其底层原理和实现机制。从学术角度来看，检索排序优化的研究可以追溯到人工智能的早期阶段。早在 1950 年代，Alan Turing 就提出了关于

AI Agent技术社区

所有评论(0)

查看更多评论

YSRM

@weixin_58628068

已为社区贡献14条内容

Leetcode+Java+图论+最短路径问题

YSRM

47.参加科学大会

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

94.城市间货物运输I

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

Bellman-Ford算法

95.城市间货物运输II

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

Bellman-Ford + 负权回路检测

96.城市间货物运输III

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

限制版Bellman-Ford

路径长度限制

97.小明逛公园

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

Floyd-Warshall算法

执行流程

127.骑士的攻击

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

A*搜索算法

骑士移动规则

启发函数

所有评论(0)

温馨提示：您尚未绑定手机号

YSRM

**A*搜索算法**