笔试时间：2025年9月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

在P2P网络传输中，节点的处理能力和链路的可用带宽直接影响数据传输的可行性。每个节点有最大可用带宽，每条链路有剩余带宽和传输延迟。当需要传输大小为D的数据包时，路径上的"所有节点"必须满足剩余带宽≥D，且路径上的"所有链路"剩余带宽也≥D。请设计算法，找到满足条件的最小总延迟路径。输出满足条件的最小总延迟。若不存在合法路径，输出-1。

输入描述

输出描述

输出满足条件的最小总延迟。若不存在合法路径，输出-1。

样例输入

4,0,3,[10,5,8,7],[[0,1,4,2],[0,2,5,3],[1,2,3,1],[1,3,2,5],[2,3,4,5]],3

样例输出

8

样例说明1

所有节点的带宽都需要≥3:

• 节点0: 10≥3 ✓
• 节点1: 5≥3 ✓
• 节点2: 8≥3 ✓
• 节点3: 7≥3 ✓

链路带宽都需要≥3:

• [0,1,4,2]: 带宽4≥3 ✓, 延迟2
• [0,2,5,3]: 带宽5≥3 ✓, 延迟3
• [1,2,3,1]: 带宽3≥3 ✓, 延迟1
• [1,3,2,5]: 带宽2<3 ✗, 不满足约束
• [2,3,4,5]: 带宽4≥3 ✓, 延迟5

可能的路径:

1. 0→2→3: 总延迟=3+5=8
2. 0→1→2→3: 总延迟=2+1+5=8

参考题解

解题思路：

1. 过滤图结构：根据数据传输量d的要求，对原始的图进行筛选，只保留节点可用带宽和链路剩余带宽都大于等于d的部分
2. 最短路径搜索：在筛选后的新图上，使用Dijkstra算法寻找从源节点s到目标节点t的延迟最小的路径
3. 返回结果：如果能找到路径，返回最小总延迟；否则返回-1

C++：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    int find_min_delay_path(int n, int s, int t, vector<int>& node_bandwidths, 
                           vector<vector<int>>& edges, int d) {
        if (node_bandwidths[s] < d || node_bandwidths[t] < d) {
            return -1;
        }
        
        vector<vector<pair<int, int>>> adj(n);
        
        for (auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int bandwidth = edge[2];
            int delay = edge[3];
            
            if (node_bandwidths[u] >= d && node_bandwidths[v] >= d && bandwidth >= d) {
                adj[u].push_back({v, delay});
            }
        }
        
        vector<int> dist(n, INT_MAX);
        dist[s] = 0;
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, s});
        
        while (!pq.empty()) {
            auto [currentDelay, u] = pq.top();
            pq.pop();
            
            if (currentDelay > dist[u]) {
                continue;
            }
            
            if (u == t) {
                return dist[t];
            }
            
            for (auto& [v, delay] : adj[u]) {
                if (dist[u] + delay < dist[v]) {
                    dist[v] = dist[u] + delay;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return dist[t] == INT_MAX ? -1 : dist[t];
    }
};

Java：

import java.util.*;

public class Solution {
    public int find_min_delay_path(int n, int s, int t, int[] node_bandwidths, 
                                  int[][] edges, int d) {
        if (node_bandwidths[s] < d || node_bandwidths[t] < d) {
            return -1;
        }
        
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int bandwidth = edge[2];
            int delay = edge[3];
            
            if (node_bandwidths[u] >= d && node_bandwidths[v] >= d && bandwidth >= d) {
                adj[u].add(new int[]{v, delay});
            }
        }
        
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{s, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int currentDelay = current[1];
            
            if (currentDelay > dist[u]) {
                continue;
            }
            
            if (u == t) {
                return dist[t];
            }
            
            for (int[] neighbor : adj[u]) {
                int v = neighbor[0];
                int delay = neighbor[1];
                
                if (dist[u] + delay < dist[v]) {
                    dist[v] = dist[u] + delay;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        
        return dist[t] == Integer.MAX_VALUE ? -1 : dist[t];
    }
}

Python：

import heapq

class Solution:
    def find_min_delay_path(self, n, s, t, node_bandwidths, edges, d):
        if node_bandwidths[s] < d or node_bandwidths[t] < d:
            return -1
        
        adj = [[] for _ in range(n)]
        
        for edge in edges:
            u, v, bandwidth, delay = edge
            
            if node_bandwidths[u] >= d and node_bandwidths[v] >= d and bandwidth >= d:
                adj[u].append((v, delay))
        
        dist = [float('inf')] * n
        dist[s] = 0
        
        pq = [(0, s)]
        
        while pq:
            current_delay, u = heapq.heappop(pq)
            
            if current_delay > dist[u]: