思路

首先将地雷按照爆炸时间排序，然后用二重循环检查每个地理都能引爆哪些地雷，然后依次按照时间引爆，引爆的时候使用dfs递归进行引爆，引爆过的地理就再f中标记为false，累加实际爆炸的地雷数，超过m就输出当前地雷爆炸时间就可以了

代码

python

def main():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        a = [list(map(int, input().split())) for _ in range(n)]
        a.sort(key=lambda x: x[2])
        
        g = [[] for _ in range(n)]
        vis = [True] * n

        for i in range(n):
            for j in range(n):
                if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) <= a[i][-1]:
                    g[i].append(j)

        def dfs(u):
            if not vis[u]:
                return 0
            vis[u] = False
            return 1 + sum(dfs(v) for v in g[u])

        total = 0
        for i in range(n):
            total += dfs(i)
            if total >= m:
                print(a[i][2])
                break

main()

java

import java.util.*;

public class Main {
    static final int MAX_N = 2005;
    static boolean[] vis = new boolean[MAX_N];
    static List<Integer>[] g = new ArrayList[MAX_N];

    static {
        for (int i = 0; i < MAX_N; i++) {
            g[i] = new ArrayList<>();
        }
    }

    static int dfs(int u) {
        if (!vis[u]) return 0;
        vis[u] = false;
        int total = 1;
        for (int v : g[u]) {
            total += dfs(v);
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();

            int[][] a = new int[n][4];
            for (int i = 0; i < n; i++) {
                a[i][0] = scanner.nextInt();
                a[i][1] = scanner.nextInt();
                a[i][2] = scanner.nextInt();
                a[i][3] = scanner.nextInt();
            }

            Arrays.sort(a, Comparator.comparingInt(o -> o[2]));

            for (int i = 0; i < n; i++) {
                g[i].clear();
                vis[i] = true;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if ((long) Math.abs(a[i][0] - a[j][0]) + (long) Math.abs(a[i][1] - a[j][1]) <= (long) a[i][3]) {
                        g[i].add(j);
                    }
                }
            }

            int total = 0;
            for (int i = 0; i < n; i++) {
                total += dfs(i);
                if (total >= m) {
                    System.out.println(a[i][2]);
                    break;
                }
            }
        }
        scanner.close();
    }
}

c++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 2005;
bool vis[MAX_N];
vector<int> g[MAX_N];

int dfs(int u) {
    if (!vis[u]) return 0;
    vis[u] = false;
    int total = 1;
    for (int v : g[u]) {
        total += dfs(v);
    }
    return total;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(4));
        for (int i = 0; i < n; ++i) {
            cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        }
        sort(a.begin(), a.end(), [](const vector<int>& x, const vector<int>& y) {
            return x[2] < y[2];
        });
        for (int i = 0; i < n; ++i) {
            g[i].clear();
            vis[i] = true;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (1ll*abs(a[i][0] - a[j][0]) + 1ll*abs(a[i][1] - a[j][1]) <= 1ll*a[i][3]) {
                    g[i].push_back(j);
                }
            }
        }

        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += dfs(i);
            if (total >= m) {
                cout << a[i][2] << endl;
                break;
            }
        }
    }
    
    return 0;
}

题目内容

小美来到了一个无限大的二维平面上，平面中有$n$个地雷，其中第$i$个地雷的坐标为($x_i,y_i$),且第$t_i$秒它就会爆炸，它的爆炸冲击会引爆和它曼哈顿距离在$k_i$以内的所有其它地雷。小美现在想知道，至少需要多长时间，才能使得至少$m$个地雷爆炸。 ($x_1,y_1$) 和($x_2, y_2$)的曼哈顿距离定义为:$dist =|x1 - x2|+|y1-y2|$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤100$)代表数据组数，每组测试数据描述如下: 第一行输入两个整数$n,m$($1≤m≤n≤2000$)，表示平面中地雷的个数和至少需要$m$个地雷爆炸。 此后$n$行,第$i$行输入四个整数 $x_i,Y_i,t_i,k_i$($-10^9≤x,y≤10^9,0≤t_i≤10^9,0≤k_i≤2x10^9$),描述第$i$个地雷。 除此之外，保证所有的$n$之和不超过$3000$。

输出描述

在一行上输出一个整数，代表最少的等待时间

样例1

输入

1
3 3
0 0 0 1
1 0 1 1
2 2 3 10

输出

3