rust 解法, 执行用时: 8 ms, 内存消耗: 2.5 MB, 提交时间: 2023-11-14 00:16:00

const INF:i32 = i32::max_value();
impl Solution {
    pub fn find_the_city(n: i32, edges: Vec<Vec<i32>>, distance_threshold: i32) -> i32 {
        let n = n as usize;
        let mut dis_table = vec![vec![INF;n];n];
        // init table
        for edge in edges {
            let city1 = edge[0] as usize;
            let city2 = edge[1] as usize;
            let dis = edge[2] as i32;
            dis_table[city1][city2] = dis;
            dis_table[city2][city1] = dis;
        }

        for city_index in 0..n {dis_table[city_index][city_index] = 0;}

        // Floyd
        for city_node in 0..n {
            for city_a in 0..n {
                for city_b in 0..n {
                    // from a to b by node
                    let dis_a:i32 = dis_table[city_node][city_a];
                    let dis_b:i32 = dis_table[city_node][city_b];
                    let dis_by_node = dis_a.saturating_add(dis_b);
                    if dis_table[city_a][city_b] > dis_by_node {
                        dis_table[city_a][city_b] = dis_by_node;
                        dis_table[city_b][city_a] = dis_by_node;
                    }
                }
            }
        }
        // Trust me, there`s no INF by now.

        // Stat Part
        let mut city_least_neighbor = n;
        let mut least_record = INF;
        for city in 0..n {
            let mut neighbor_count = 0;
            for dstn in 0..n {
                if dis_table[city][dstn] <= distance_threshold { neighbor_count+=1; }
            }
            if neighbor_count < least_record {
                city_least_neighbor = city;
                least_record = neighbor_count;
            } else if neighbor_count == least_record {
                if city > city_least_neighbor {city_least_neighbor = city;}
            } 
        }
        // return as i32
        city_least_neighbor as i32
    }
}

python3 解法, 执行用时: 348 ms, 内存消耗: 17.4 MB, 提交时间: 2023-10-24 07:49:26

import heapq

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dct = defaultdict(dict)
        for i, j, w in edges:
            dct[i][j] = w
            dct[j][i] = w

        ans = -1
        reach = n+1
        for i in range(n):
            cnt = set()
            stack = [[0, i]]
            while stack:
                dis, cur = heapq.heappop(stack)
                if dis > distanceThreshold:
                    break

                if cur in cnt:
                    continue
                cnt.add(cur)
                if len(cnt) > reach:
                    break

                for nex in dct[cur]:
                    if nex not in cnt:
                        heapq.heappush(stack, [dis+dct[cur][nex], nex])
                        
            if len(cnt) <= reach:
                ans = i
                reach = len(cnt)
        return ans

python3 解法, 执行用时: 568 ms, 内存消耗: 17.3 MB, 提交时间: 2023-10-24 07:48:59

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis=[[float('inf') for _ in range(n)] for _ in range(n)]
        for i in range(n):dis[i][i]=0
        for i,j,w in edges:
            dis[i][j]=w
            dis[j][i]=w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
        res,count=0,n+1
        for i in range(n):
            cur=0
            for j in range(n):
                if dis[i][j]<=distanceThreshold:
                    cur+=1
            if cur<=count:
                res,count=i,cur
        return res

golang 解法, 执行用时: 16 ms, 内存消耗: 5.3 MB, 提交时间: 2023-10-24 07:48:38

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	// 定义邻接矩阵
	var dp [][]int
	for i := 0; i < n; i++ {
		var tmp []int
		for j := 0; j < n; j++ {
			if i == j {
				tmp = append(tmp, 0)
			} else {
				tmp = append(tmp, -1)
			}
		}
		dp = append(dp, tmp)
	}

	// 填出边长度
	for i := 0; i < len(edges); i++ {
		from := edges[i][0]
		to := edges[i][1]
		weight := edges[i][2]
		// 无向图
		dp[from][to] = weight
		dp[to][from] = weight
	}

	// dp转移方程
	// 将k放在第一层,后面的值依赖k
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				// 相同节点跳过
				if i == j || j == k || i == k {
					continue
				}
				// 不通路也跳过
				if dp[i][k] == -1 || dp[k][j] == -1 {
					continue
				}
				tmp := dp[i][k] + dp[k][j]
				if dp[i][j] == -1 || dp[i][j] > tmp {
					dp[i][j] = tmp
					dp[j][i] = tmp
				}
			}
		}
	}
	min := n
	idx := 0
	for i := 0; i < n; i++ {
		cnt := 0
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			if dp[i][j] <= distanceThreshold {
				cnt++
			}
		}
		if cnt <= min {
			min = cnt
			idx = i
		}
	}
	return idx
}

golang 解法, 执行用时: 24 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-24 07:48:25

const inf = 0x3f3f3f3f

type edge struct {
	x    int
	time int
} // 定义边结构体，字段为到to节点，和到to的时间

// go 语言中，不提供有限队列数据结构，需要结合heap自己实现
type hp []edge

func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].time < h[j].time }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(edge)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

func dijkstraStart(graphs [][]edge, n int, start int) []int {
	dist := make([]int, n)

	for i := 0; i < n; i++ {
		dist[i] = inf
	}

	h := &hp{}
	heap.Init(h)

	heap.Push(h, edge{x: start, time: 0})
	dist[start] = 0

	for h.Len() > 0 {
		node := heap.Pop(h).(edge)
		cur, curdist := node.x, node.time

		if dist[cur] < curdist { // 0 肯定不可能大于 d，所以第一次一定不走这个
			continue
		}

		for _, nextNode := range graphs[cur] {
			next, nextdist := nextNode.x, nextNode.time

			if nextdist+dist[cur] < dist[next] {
				dist[next] = nextdist + dist[cur]
				heap.Push(h, edge{x: next, time: dist[next]})
			}
		}
	}

	return dist
}

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	graph := make([][]edge, n)
	for _, ev := range edges {
		graph[ev[0]] = append(graph[ev[0]], edge{x: ev[1], time: ev[2]})
		graph[ev[1]] = append(graph[ev[1]], edge{x: ev[0], time: ev[2]})
	}

	toCityMax := math.MaxInt32
    cityIdx := -1

	for i := 0; i < n; i++ {
		dist := dijkstraStart(graph, n, i)

		count := 0
		for _, dv := range dist {
			if dv > 0 && dv <= distanceThreshold {
				count++
			}
		}

        if toCityMax >= count {
            toCityMax = count
            cityIdx = i
        }
	}

	return cityIdx
}

java 解法, 执行用时: 17 ms, 内存消耗: 41.9 MB, 提交时间: 2023-10-24 07:47:47

class Solution {
    // dijkstra
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] map = new int[n][n];
        final int INF = 0x3f3f3f3f;
        //init map
        for (int[] ints : map) {
            Arrays.fill(ints, INF);
        }
        for (int i = 0; i < n; i++) {
            map[i][i] = 0;
        }
        for (int[] e : edges) {
            map[e[0]][e[1]] = map[e[1]][e[0]] = e[2];
        }
        int res = 0;
        int MIN = n + 1;

        for (int i = 0; i < n; i++) {
            int[] dist = new int[n];
            boolean[] set = new boolean[n];
            for (int v = 0; v < n; v++) {
                dist[v] = map[i][v];
            }
            dist[i] = 0;
            set[i] = true;
            for (int j = 0; j < n - 1; j++) {
                int min = INF;
                int start = i;
                for (int k = 0; k < n; k++) {
                    if (!set[k] && dist[k] < min) {
                        min = dist[k];
                        start = k;
                       }
                }
                set[start] = true;
                for (int k = 0; k < n; k++) {
                    if (!set[k] && dist[k] > dist[start] + map[start][k]) {
                        dist[k] = dist[start] + map[start][k];
                    }
                }
            }
            int temp = 0;
            for (int j = 0; j < dist.length; j++) {
                if (dist[j] <= distanceThreshold) {
                    temp++;
                }
            }
            if (temp <= MIN) {
                MIN = temp;
                res = i;
            }
        }
        return res;
    }

    // floyd
    public static int findTheCity2(int n, int[][] edges, int distanceThreshold) {
        int[][] map = new int[n][n];

        //init
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    map[i][j] = 0;
                } else {
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        //get map 
        for (int[] e : edges) {
            map[e[0]][e[1]] = map[e[1]][e[0]] = e[2];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != k && j != k && map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }
        }

        //get res
        int min = n + 1;
        int res = -1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && map[i][j] <= distanceThreshold) {
                    count++;
                }
            }
            if (min >= count) {
                min = count;
                res = i;
            }
        }
        return res;
    }
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 43 MB, 提交时间: 2023-10-24 07:46:24

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} distanceThreshold
 * @return {number}
 */
const findTheCity = (n, edges, distanceThreshold) => {
  const MAX = 10001;
  const distance = Array.from({ length: n }, () => new Uint16Array(n).fill(MAX));
  for (const edge of edges) {
    distance[edge[0]][edge[1]] = distance[edge[1]][edge[0]] = edge[2];
  }
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
      if (i === j || distance[j][i] === MAX) continue;
      for (let k = j + 1; k < n; ++k) {
        distance[k][j] = distance[j][k] = Math.min(distance[j][k], distance[j][i] + distance[i][k]);
      }
    }
  }

  let city = 0;
  let minNum = n;
  for (let i = 0; i < n; ++i) {
    let curNum = 0;
    for (let j = 0; j < n; ++j) {
      distance[i][j] <= distanceThreshold && ++curNum;
    }
    if (curNum <= minNum) { minNum = curNum; city = i; }
  }
  return city;
};

cpp 解法, 执行用时: 36 ms, 内存消耗: 11.6 MB, 提交时间: 2023-10-24 07:45:07

class Solution {
public:
    void dijkstra(int graph[101][101], int dist[101], int v, int n) {
        // 初始化 dist
        for (int i = 0; i < n;  i++) {
            dist[i] = graph[v][i];
        }
        // 标记当前点是否已经加入集合
        bool m[101];
        memset(m, 0, sizeof(m));
        m[v] = true;

        // 每次都找离集合最近的一个点，一共要找 n-1 次
        for (int k = 0; k < n-1; k ++) {
            int minv = INT_MAX;
            int next = v;
            for (int i = 0; i < n; i ++) {
                if (!m[i] && dist[i] < minv) {
                    minv = dist[i];
                    next = i;
                }
            }
            m[next] = true;
            // 每次找到最近的点，并用它更新其它点到集合的距离，
            // 也就是更新dist数组
            for (int i = 0; i < n; i ++) {
                if (m[i] || graph[next][i] == INT_MAX) {
                    continue;
                }
                dist[i] = min(dist[i], dist[next] + graph[next][i]);
            }
        }
    }

    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        // 定义并初始化邻接矩阵 graph
        int graph[101][101];
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                graph[i][j] = INT_MAX;
            }
        }
        for (auto& edge : edges) {
            graph[edge[0]][edge[1]] = edge[2];
            graph[edge[1]][edge[0]] = edge[2];
        }

        int mincnt = INT_MAX;
        int ret = 0;
        for (int i = 0; i < n; i ++) {
            // 使用单源最短路径dijkstra算法生成：
            // 以i为源点到其它各点的最短路径数组dist
            int dist[101];
            dijkstra(graph, dist, i, n);
            
            int cnt = 0;
            for (int j = 0; j < n; j ++) {
                if (dist[j] <= distanceThreshold) {
                    cnt ++;
                }
            }
            if (cnt <= mincnt) {
                mincnt = cnt;
                ret = i;
            }
        }
        return ret;
    }
};

cpp 解法, 执行用时: 84 ms, 内存消耗: 12 MB, 提交时间: 2023-10-24 07:44:45

class Solution {
public:
    // floyd 算法 d[i][j], 表示i到j的距离
    int findTheCity(int n, vector <vector<int>> &edges, int distanceThreshold) {
        // 定义邻接矩阵D，并初始化各个城市间距离为INT_MAX（无穷）
        vector <vector<int>> D(n, vector<int>(n, INT_MAX));
        // 根据edges[][]初始化D[][]
        for (auto &e : edges) {
            // 无向图两个城市间的两个方向距离相同
            D[e[0]][e[1]] = e[2];
            D[e[1]][e[0]] = e[2];
        }
        // Floyd算法
        for (int k = 0; k < n; k++) {
            // n个顶点依次作为插入点
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j || D[i][k] == INT_MAX || D[k][j] == INT_MAX) {
                        // 这些情况都不符合下一行的if条件，
                        // 单独拿出来只是为了防止两个INT_MAX相加导致溢出
                        continue;
                    }
                    D[i][j] = min(D[i][k] + D[k][j], D[i][j]);
                }
            }
        }
        // 选择出能到达其它城市最少的城市ret
        int ret;
        int minNum = INT_MAX;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && D[i][j] <= distanceThreshold) {
                    cnt++;
                }
            }
            if (cnt <= minNum) {
                minNum = cnt;
                ret = i;
            }
        }
        return ret;
    }
};