✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线160+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东

题目一：城市快递路线优化

1️⃣：将特殊传送设备视为权值为0的双向边加入图中

2️⃣：使用Dijkstra算法求解带权无向图的最短路径问题

难度：中等

这道题目是经典的最短路问题的变种，关键在于理解特殊传送设备可以看作一条权值为0的边。通过在原图基础上添加这条特殊边，问题转化为标准的单源最短路问题，使用Dijkstra算法即可高效求解。

题目二：书籍序列排列统计

1️⃣：使用双向动态规划分别计算前缀和后缀的LIS信息

2️⃣：利用树状数组优化DP过程，维护最优状态

3️⃣：合并前后两个方向的结果，统计包含每个位置的LIS数量

难度：中等偏难

这道题目是最长递增子序列（LIS）的进阶问题，需要统计每个位置被多少条不同的LIS包含。通过前缀DP和后缀DP分别计算两个方向的信息，再结合树状数组优化，可以在O(n log n)时间内解决问题，体现了动态规划与数据结构结合的精妙之处。

01. 城市快递路线优化

问题描述

小兰是一名快递配送规划师，负责优化城市间的配送路线。城市交通网络中有 个配送站点（编号为 到 ），站点之间有 条交通路线，每条路线的通行时间是固定的。

小兰需要规划从起始站点到目标站点的最短配送时间。值得注意的是，由于技术合作协议，在某两个特定站点之间安装了高速传送设备，可以在这两个站点间瞬间传输货物（传输时间为 分钟），且可以双向使用。

请帮助小兰计算从起始站点到目标站点的最短配送时间。

输入格式

第一行包含两个正整数 ，分别表示配送站点数量和交通路线数量。

第二行包含两个正整数 ，分别表示起始站点编号和目标站点编号。

第三行包含两个正整数 ，表示安装了高速传送设备的两个站点编号。

接下来 行，每行包含三个正整数 ，表示站点 和站点 之间有一条双向交通路线，通行时间为 分钟。

输出格式

输出一个整数，表示从起始站点到目标站点的最短配送时间。

样例输入

6 5
2 6
3 5
2 3 3
3 4 2
4 5 1
5 6 4
2 4 5

样例输出

7

数据范围

• 
• 
• 
• ，

题解

这道题本质上是一个带有特殊边的最短路问题。

关键思路是将高速传送设备看作一条权值为 的双向边。这样原问题就转化为了在一个包含 个顶点、 条边的加权无向图中，求从起点 到终点 的最短路径。

算法步骤：

1. 构建图的邻接表，将所有原始交通路线加入图中
2. 在站点 和站点 之间添加一条权值为 的双向边，表示传送设备
3. 使用 Dijkstra 算法计算从起点 到终点 的最短路径

由于所有边的权值都是非负的（原始路线权值为正，传送设备权值为 ），可以直接使用 Dijkstra 算法。对于给定的数据规模（），时间复杂度 完全可以满足要求。

特殊情况处理：如果起点和终点本身就是传送设备连接的两个站点，那么传送设备会让路径更短；如果传送设备不在最短路径上，那么它不会影响结果。

参考代码

Python

import sys
import heapq
input = lambda: sys.stdin.readline().strip()

n, m = map(int, input().split())
s, t = map(int, input().split())
a, b = map(int, input().split())

# 构建邻接表
graph = [[] for _ in range(n + 1)]

# 添加原始交通路线
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

# 添加传送设备（权值为0的边）
graph[a].append((b, 0))
graph[b].append((a, 0))

# Dijkstra算法求最短路
dist = [float('inf')] * (n + 1)
dist[s] = 0
pq = [(0, s)]  # (距离, 节点)

while pq:
    d, u = heapq.heappop(pq)
    
    # 如果当前距离不是最优，跳过
    if d > dist[u]:
        continue
    
    # 到达目标站点，返回结果
    if u == t:
        break
    
    # 遍历相邻节点
    for v, w in graph[u]:
        new_dist = d + w
        if new_dist < dist[v]:
            dist[v] = new_dist
            heapq.heappush(pq, (new_dist, v))

print(dist[t])

Cpp

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    int s, t;
    cin >> s >> t;
    
    int a, b;
    cin >> a >> b;
    
    // 构建邻接表
    vector<vector<pair<int, int>>> adj(n + 1);
    
    // 添加交通路线
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    // 添加传送设备
    adj[a].push_back({b, 0});
    adj[b].push_back({a, 0});
    
    // Dijkstra算法
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, 
                   greater<pair<long long, int>>> pq;
    
    dist[s] = 0;
    pq.push({0, s});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        if (u == t) break;
        
        for (auto [v, w] : adj[u]) {
            long long new_d = d + w;
            if (new_d < dist[v]) {
                dist[v] = new_d;
                pq.push({new_d, v});
            }
        }
    }
    
    cout << dist[t] << endl;
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static class Edge {
        int to, weight;
        
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    static class State implements Comparable<State> {
        long dist;
        int node;
        
        State(long dist, int node) {
            this.dist = dist;
            this.node = node;
        }
        
        @Override
        public int compareTo(State other) {
            return Long.compare(this.dist, other.dist);
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        
        // 构建邻接表
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加交通路线
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            graph.get(u).add(new Edge(v, w));
            graph.get(v).add(new Edge(u, w));
        }
        
        // 添加传送设备
        graph.get(a).add(new Edge(b, 0));
        graph.get(b).add(new Edge(a, 0));
        
        // Dijkstra算法
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<State> pq = new PriorityQueue<>();
        
        dist[s] = 0;
        pq.offer(