| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2077 |
第 119 场双周赛 Q4 |
|
一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。
公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。
两个分部之间的 距离 是通过道路长度之和的 最小值 。
给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。
请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。
注意，关闭一个分部后，与之相连的所有道路不可通行。
注意，两个分部之间可能会有多条道路。
示例 1：
输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]] 输出：5 解释：可行的关闭分部方案有： - 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。 - 关闭分部集合 [0,1] ，剩余分部为 [2] 。 - 关闭分部集合 [1,2] ，剩余分部为 [0] 。 - 关闭分部集合 [0,2] ，剩余分部为 [1] 。 - 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。 总共有 5 种可行的关闭方案。
示例 2：
输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]] 输出：7 解释：可行的关闭分部方案有： - 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。 - 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。 - 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。 - 关闭分部集合 [0,1] ，剩余分部为 [2] 。 - 关闭分部集合 [1,2] ，剩余分部为 [0] 。 - 关闭分部集合 [0,2] ，剩余分部为 [1] 。 - 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。 总共有 7 种可行的关闭方案。
示例 3：
输入：n = 1, maxDistance = 10, roads = [] 输出：2 解释：可行的关闭分部方案有： - 关闭分部集合 [] ，剩余分部为 [0] 。 - 关闭分部集合 [0] ，关闭后没有剩余分部。 总共有 2 种可行的关闭方案。
提示：
1 <= n <= 101 <= maxDistance <= 1050 <= roads.length <= 1000roads[i].length == 30 <= ui, vi <= n - 1ui != vi1 <= wi <= 1000- 一开始所有分部之间通过道路互相可以到达。
我们注意到
对于每个分部集合，我们可以使用 Floyd 算法来计算出剩余分部之间的最短距离，然后判断是否满足题目要求即可。具体地，我们先枚举中间点
时间复杂度
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
ans = 0
for mask in range(1 << n):
g = [[inf] * n for _ in range(n)]
for u, v, w in roads:
if mask >> u & 1 and mask >> v & 1:
g[u][v] = min(g[u][v], w)
g[v][u] = min(g[v][u], w)
for k in range(n):
if mask >> k & 1:
g[k][k] = 0
for i in range(n):
for j in range(n):
# g[i][j] = min(g[i][j], g[i][k] + g[k][j])
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
if all(
g[i][j] <= maxDistance
for i in range(n)
for j in range(n)
if mask >> i & 1 and mask >> j & 1
):
ans += 1
return ansclass Solution {
public int numberOfSets(int n, int maxDistance, int[][] roads) {
int ans = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
int[][] g = new int[n][n];
for (var e : g) {
Arrays.fill(e, 1 << 29);
}
for (var e : roads) {
int u = e[0], v = e[1], w = e[2];
if ((mask >> u & 1) == 1 && (mask >> v & 1) == 1) {
g[u][v] = Math.min(g[u][v], w);
g[v][u] = Math.min(g[v][u], w);
}
}
for (int k = 0; k < n; ++k) {
if ((mask >> k & 1) == 1) {
g[k][k] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
int ok = 1;
for (int i = 0; i < n && ok == 1; ++i) {
for (int j = 0; j < n && ok == 1; ++j) {
if ((mask >> i & 1) == 1 && (mask >> j & 1) == 1) {
if (g[i][j] > maxDistance) {
ok = 0;
}
}
}
}
ans += ok;
}
return ans;
}
}class Solution {
public:
int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
int ans = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
int g[n][n];
memset(g, 0x3f, sizeof(g));
for (auto& e : roads) {
int u = e[0], v = e[1], w = e[2];
if ((mask >> u & 1) & (mask >> v & 1)) {
g[u][v] = min(g[u][v], w);
g[v][u] = min(g[v][u], w);
}
}
for (int k = 0; k < n; ++k) {
if (mask >> k & 1) {
g[k][k] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
int ok = 1;
for (int i = 0; i < n && ok == 1; ++i) {
for (int j = 0; j < n && ok == 1; ++j) {
if ((mask >> i & 1) & (mask >> j & 1) && g[i][j] > maxDistance) {
ok = 0;
}
}
}
ans += ok;
}
return ans;
}
};func numberOfSets(n int, maxDistance int, roads [][]int) (ans int) {
for mask := 0; mask < 1<<n; mask++ {
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = 1 << 29
}
}
for _, e := range roads {
u, v, w := e[0], e[1], e[2]
if mask>>u&1 == 1 && mask>>v&1 == 1 {
g[u][v] = min(g[u][v], w)
g[v][u] = min(g[v][u], w)
}
}
for k := 0; k < n; k++ {
if mask>>k&1 == 1 {
g[k][k] = 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
g[i][j] = min(g[i][j], g[i][k]+g[k][j])
}
}
}
}
ok := 1
for i := 0; i < n && ok == 1; i++ {
for j := 0; j < n && ok == 1; j++ {
if mask>>i&1 == 1 && mask>>j&1 == 1 && g[i][j] > maxDistance {
ok = 0
}
}
}
ans += ok
}
return
}function numberOfSets(n: number, maxDistance: number, roads: number[][]): number {
let ans = 0;
for (let mask = 0; mask < 1 << n; ++mask) {
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
for (const [u, v, w] of roads) {
if ((mask >> u) & 1 && (mask >> v) & 1) {
g[u][v] = Math.min(g[u][v], w);
g[v][u] = Math.min(g[v][u], w);
}
}
for (let k = 0; k < n; ++k) {
if ((mask >> k) & 1) {
g[k][k] = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
let ok = 1;
for (let i = 0; i < n && ok; ++i) {
for (let j = 0; j < n && ok; ++j) {
if ((mask >> i) & 1 && (mask >> j) & 1 && g[i][j] > maxDistance) {
ok = 0;
}
}
}
ans += ok;
}
return ans;
}