【每日一题】阈值距离内邻居最少的城市

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：多源最短路
写在最后

Tag

【多源最短路】【数组】【2023-11-14】

题目来源

1334. 阈值距离内邻居最少的城市

题目解读

题目翻译过来是这样的：一共 n 个城市，统计在每个城市 dt 距离范围内所有的其他城市的数目的最小值：

如果有多个最小值，返回城市的最大编号；
否则返回唯一的城市编号。

解题思路

方法一：多源最短路

本题需要统计从每个城市出发到达其他城市的最短路径，根据 最短路径小于阈值路径 得到每个城市阈值范围内的可到达城市数量，最后返回最少可到达城市对应的最大编号的出发城市。

实现上，从大到小枚举城市编号作为出发城市，计算该城市阈值范围内的可到达城市数量，如果后续枚举的城市有更小的可到达城市数量，则更新后续的城市为新的答案，否则当前枚举的城市就是最后的答案。

如何某个城市阈值范围内的可到达城市数量？

这是单源最短路径问题。首先根据 edges 建立边权图 mat，二维数组 mat 初始化为 -1根据 edges 数组更新一些边之间的权重。

维护一个数组 dist，表示从城市 u 出发到达某个城市的最小距离，初始化为 -1。接着利用广度优先搜索从 u 向外扩展，更新 u 到其他城市的最小距离，具体地：

初始化队列 q，源点 u 入队，dist[u] = 0；
依次从队列中取出节点 t，直到队列为空：
- 先进行一次剪枝，如果 dist[t] > dt，（dt 是题目设置的距离阈值）直接跳过节点 t，重新选取节点出发。
- 枚举其他所有城市节点 i，如果 mat[t][i] = -1，则跳过当前节点（城市节点 t 和 i 无法相到达）：
  - 更新 u 到当前城市 i 的最短距离，如果 dist[i] = -1 或者经城市 t 到城市 i 比直接从城市 u 到 i 距离小，则更新 u 到当前城市 i 的最短距离为中转方案的最小距离，并将 i 加入队列中；
队列为空后，统计从 dist[i] != -1 的数量 cnt，即为从城市 u 出发阈值范围内的可到达城市数量。

以下是具有 C 语言风格的 C++ 代码。

实现代码

#define maxn 110
#define inf -1

class Solution {
private：
    int mat[maxn][maxn];

    int Min(int a, int b){
        if(a == inf) return b;
        if(b == inf) return a;
        return a < b ? a : b;
    }

    // 计算从 u 城市出发，在 dt 范围内能到达的城市数量，一共是 n 个城市
    int spfa(int n, int u, int dt){
        int i;
        queue<int> q;
        int dist[maxn];         // 从城市 u 出发到达某个城市的距离
        memset(dist, inf, sizeof(dist));
        dist[u] = 0;
        q.push(u);

        while(!q.empty()){
            int t = q.front();
            q.pop();
            if(dist[t] > dt){
                continue;
            }
            for(i = 0; i < n; ++i){
                if(mat[t][i] == inf){
                    continue;// 说明 t 城市无法到 i 城市
                }
                int toDist = dist[t] + mat[t][i];   // 从城市u到城市i的距离
                if(dist[i] == inf || toDist < dist[i]){
                    dist[i] = toDist;
                    q.push(i);
                }
            }
        }
        int cnt = 0;
        for(i = 0; i < n; ++i){
            if(dist[i] != inf && dist[i] <= dt){
                ++cnt;
            }
        }
        return cnt;
    }
public:
    int findTheCity(int n, vector<vector<int>>& edges, int dt) {
        int i;
        int retId, retCnt;

        memset(mat, inf, sizeof(mat));
        for(i = 0; i < edges.size(); ++i){
            int u = edges[i][0];
            int v = edges[i][1];
            int w = edges[i][2];
            mat[u][v] = mat[v][u] = Min(mat[u][v], w);
        }

        retCnt = 110;
        for(i = n - 1; i >= 0; --i){
            int cnt = spfa(n, i, dt);
            if(cnt < retCnt){      // 找出城市数目最少的最大编号
                retCnt = cnt;
                retId = i;
            }
        }
        return retId;
    }
};