题面描述:

塔子哥需要在多个业务节点之间选择最快的逃生节点，同时考虑各节点的剩余业务容量。输入包括一个网络时延矩阵，表示节点之间的通信延迟，以及一个剩余容量列表，表示每个节点的可用业务容量。在发生节点故障时，塔子哥需要找到一个或多个逃生节点，确保逃生路径的延迟最小，并且这些节点的总容量足够容纳故障节点的业务量。如果有多个合适的逃生节点，优先选择编号较小的节点；如果没有节点满足条件，则返回所有容量足够的节点。

思路

本题是个阅读理解，读懂了就应该会发现其实就是考察了最短路怎么求。

以故障点为源点求完最短路后，根据距离从小到大排序后，依次选取即可。

题解

在这道题目中，我们需要根据故障节点的信息，计算其他业务节点到故障节点的最短路径，并根据这些路径的延迟和剩余业务容量选择合适的逃生节点。解决方案主要分为以下几个步骤：

1. 输入读取：读取节点数、延迟矩阵、剩余容量、故障节点编号和故障节点的业务量。
2. 最短路径计算：使用 Dijkstra 算法从故障节点出发计算到其他节点的最短路径。
3. 结果筛选：根据最短路径的长度和剩余容量筛选合适的逃生节点，并输出结果。

AC代码

C++

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

typedef long long LL;

int main (){
    ios::sync_with_stdio(false); // 加快输入输出速度
    std::cin.tie(0);
    
    int n; 
    cin >> n; // 读取节点数
    vector<vector<int>> g(n, vector<int>(n)); // 创建延迟矩阵
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            cin >> g[i][j]; // 读取延迟值
            if(g[i][j] == -1) // 如果没有直接连接
                g[i][j] = 1e9; // 将其设为一个很大的值（无穷大）
        }
    
    vector<int> cost(n); // 创建剩余容量数组
    for(int i = 0; i < n; i++)
        cin >> cost[i]; // 读取每个节点的剩余容量

    int wr; 
    cin >> wr; // 读取故障节点编号
    int ned; 
    cin >> ned; // 读取需要迁移的业务量

    vector<int> d(n + 1, 1e9); // 创建距离数组，初始化为无穷大
    vector<bool> st(n + 1, false); // 创建标记数组，表示节点是否已确定最短路径

    // Dijkstra 算法实现
    auto dij = [&]() {
        d[wr] = 0; // 故障节点到自身的距离为 0
        for(int i = 0; i < n - 1; i++)
        {
            int t = -1; // 选择下一个节点
            for(int j = 0; j < n; j++)
                if(!st[j] && (t == -1 || d[j] < d[t])) // 找到距离最小的未标记节点
                    t = j;

            for(int j = 0; j < n; j++)
                d[j] = min(d[j], d[t] + g[t][j]); // 更新其他节点的距离
            
            st[t] = true; // 标记节点 t
        }
        d[wr] = 1e9; // 恢复故障节点的距离为无穷大，避免再次使用
    };

    dij(); // 执行 Dijkstra 算法

    vector<array<int, 3>> ans(n); // 存储节点的信息（距离、节点编号、剩余容量）
    for(int i = 0; i < n; i++)
    {
        ans[i] = {d[i], i, cost[i]}; // 初始化信息
    }
    sort(ans.begin(), ans.end()); // 按照距离从小到大排序

    int cur = 0; // 当前已选节点的总容量
    vector<int> res; // 存储最终结果
    for(int i = 0; i < n; i++)
    {
        auto t = ans[i];
        if(t[0] >= 1e9) // 如果距离为无穷大，停止
            break;    
        
        cur += t[2]; // 累加当前节点的剩余容量
        res.push_back(t[1]); // 记录当前节点编号
        if(cur >= ned) // 如果当前容量已满足要求，停止
            break;
    } 
    
    int sz = res.size(); // 结果数量
    for(int i = 0; i < sz; i++)
        cout << res[i] << " \n"[i == sz - 1]; // 输出结果，用空格分隔
    return 0;
}

python

# 读取节点数
n = int(input())

# 初始化邻接矩阵
adj = []
for i in range(n):
    # 读取每个节点之间的延迟，并构建邻接矩阵
    adj.append(list(map(int, input().split())))

# 读取每个节点的剩余容量
cap = list(map(int, input().split()))

# 读取故障节点的编号
fault = int(input())

# 读取需要迁移的业务量
amount = int(input())

import heapq  # 导入堆（优先队列）模块

# 设置无穷大
inf = 1000000

# 初始化距离数组，默认值为无穷大
dist = [inf] * n

# 故障节点到自身的距离为 0
dist[fault] = 0

# 初始化优先队列，将故障节点加入队列
q = [[0, fault]]

# 访问标记数组，表示节点是否已确定最短路径
vis = [False] * n

# Dijkstra 算法的主循环
while q:
    # 从优先队列中取出距离最小的节点
    d, u = heapq.heappop(q)
    
    # 如果当前距离不等于记录的距离，说明该节点已被更新，跳过
    if d != dist[u]:
        continue

    # 标记当前节点为已访问
    vis[u] = True

    # 遍历所有邻接节点
    for v in range(n):
        # 如果节点 v 未访问且 u 到 v 的边存在
        if not vis[v] and adj[u][v] != -1 and dist[v] > dist[u] + adj[u][v]:
            # 更新 v 的最短距离
            dist[v] = dist[u] + adj[u][v]
            # 将更新后的节点加入优先队列
            heapq.heappush(q, [dist[v], v])

# 将故障节点的距离恢复为无穷大，避免再次使用
dist[fault] = inf

# 收集所有节点的距离和编号，按照距离排序
lst = sorted([(dist[i], i) for i in range(n)])

s = 0  # 当前已选节点的总容量
ans = []  # 存储结果

# 遍历排序后的节点
for d, u in lst:
    if u == fault:  # 遇到故障节点时停止
        break
    s += cap[u]  # 累加当前节点的剩余容量
    ans.append(u)  # 记录当前节点编号
    if s > amount:  # 如果当前容量已满足要求，停止
        break

# 输出结果，用空格分隔
print(' '.join(map(str, ans)))

java

import java.util.*;

public class Main {
    static final int INF = (int) 1e9;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt(); // 读取节点数量
        int[][] g = new int[n][n]; // 创建延迟矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = scanner.nextInt(); // 读取延迟值
                if (g[i][j] == -1) g[i][j] = INF; // 无连接设为无穷大
            }
        }

        int[] cost = new int[n]; // 剩余容量数组
        for (int i = 0; i < n; i++) {
            cost[i] = scanner.nextInt(); // 读取每个节点的剩余容量
        }

        int wr = scanner.nextInt(); // 故障节点编号
        int ned = scanner.nextInt(); // 需要迁移的业务量

        int[] d = new int[n]; // 最短路径数组
        boolean[] st = new boolean[n]; // 标记数组
        Arrays.fill(d, INF); // 初始化距离为无穷大

        // Dijkstra 算法
        d[wr] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 0; j < n; j++) {
                if (!st[j] && (t == -1 || d[j] < d[t])) {
                    t = j;
                }
            }
            if (t == -1 || d[t] == INF) break; // 无法继续扩展

            st[t] = true; // 标记该节点

            for (int j = 0; j < n; j++) {
                d[j] = Math.min(d[j], d[t] + g[t][j]); // 更新最短路径
            }
        }
        d[wr] = INF; // 恢复故障节点的距离

        // 存储 (距离, 节点编号, 剩余容量)
        List<int[]> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ans.add(new int[]{d[i], i, cost[i]});
        }

        // 按距离排序
        ans.sort(Comparator.comparingInt(a -> a[0]));

        int cur = 0; // 当前已选节点的总容量
        List<Integer> res = new ArrayList<>();

        // 选择满足需求的节点
        for (int[] t : ans) {
            if (t[0] >= INF) break; // 距离无穷大时停止

            cur += t[2]; // 累加当前节点的剩余容量
            res.add(t[1]); // 记录当前节点编号
            if (cur >= ned) break; // 如果达到需求，停止
        }

        // 输出结果
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i));
            if (i != res.size() - 1) System.out.print(" ");
        }
        System.out.println();

        scanner.close();
    }
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const INF = 1e9;

    // 读取节点数
    let n = parseInt(await readline());

    // 读取延迟矩阵
    let g = Array.from({ length: n }, () => Array(n).fill(INF));
    for (let i = 0; i < n; i++) {
        let row = (await readline()).split(" ").map(Number);
        for (let j = 0; j < n; j++) {
            g[i][j] = row[j] === -1 ? INF : row[j];
        }
    }

    // 读取剩余容量
    let cost = (await readline()).split(" ").map(Number);

    // 读取故障节点和需要迁移的业务量
    let wr = parseInt(await readline());
    let ned = parseInt(await readline());

    // Dijkstra 算法
    let d = Array(n).fill(INF);
    let st = Array(n).fill(false);

    function dijkstra() {
        d[wr] = 0;

        for (let i = 0; i < n - 1; i++) {
            let t = -1;
            for (let j = 0; j < n; j++) {
                if (!st[j] && (t === -1 || d[j] < d[t])) {
                    t = j;
                }
            }

            if (t === -1 || d[t] === INF) break;

            st[t] = true;

            for (let j = 0; j < n; j++) {
                d[j] = Math.min(d[j], d[t] + g[t][j]);
            }
        }

        d[wr] = INF; // 恢复故障节点的距离，防止被选中
    }

    dijkstra();

    // 存储 (距离, 节点编号, 剩余容量)
    let ans = [];
    for (let i = 0; i < n; i++) {
        ans.push([d[i], i, cost[i]]);
    }

    // 按照距离排序
    ans.sort((a, b) => a[0] - b[0]);

    let cur = 0; // 当前已选节点的总容量
    let res = [];

    // 选择满足需求的节点
    for (let i = 0; i < n; i++) {
        let [dist, node, capacity] = ans[i];
        if (dist >= INF) break;

        cur += capacity;
        res.push(node);
        if (cur >= ned) break;
    }

    console.log(res.join(" "));

    rl.close();
})();

题目描述

小明需要多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。业务节点之间的关系可以看作一个图。小明有一个网络时延表，表示每个节点到其他节点的通信延迟，即小明从某节点逃到另一节点所需要的时间;还有一个剩余业务容量表，表示每个节点的剩余业务容量。在一个节点故障时，需要选择一个或多个逃生节点，确保逃生路径的时延最小，并且逃生节点集各节点剩余容量的总和足够容纳故障节点的业务量，当故障节点与多个节点最短距离相同，优先选择编号较小的节点容灾，如果逃生节点集中多个节点最短距离相同时按编号从小到大的顺序排列。

输入描述

第$1$行$n$表示业务节点数， $2<=n<=10000$，节点编号从 $0$ 开始，依次递增；

第$2$到$1+n$行表示业务节点间的网络时延矩阵表 delayMatrix，$delayMatrix[i][j]$ 表示节点$i$到节点$j$的通信时延;

1）如果节点$i$和节点$j$之间没有直接相连的边，则 $delayMatrix[i][j]$ 为 -1，第$i$个节点和它自己也没有边，所以$delayMatrix[i][i]=-1$

2）节点间有边时延范围为 $1<=delayMatrix[i][j]<=1000$，矩阵元素间使用空格分割 另，输入保证 $delayMatrix[i][j] == delayMatrix[j][i]$

第2+n行表示各业务节点的剩余容量表 remainingCapacity，其中 remainingCapacity[i] 表示节点 i 的剩余业务容量，业务量的范围$1<=remainingCapacity[i]<=100$，数组元素间使用空格分割；

第$3+n$行表示故障业务节点编号 faultyNode，表示发生故障的节点，取值范围为 $0<=faultyNode<=n−1$ ；

第$4+n$行表示受损业务节点需要迁移的业务量, 受损业务量的范围 (0−1000] 。

输出描述

返回符合条件的逃生路径节点编号列表，用空格分隔。当所有节点都不够故障节点业务容灾时候，输出所有容灾节点。

样例

输入

4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
12

输出

1