Description
Submission
class Solution {
static constexpr int maxLen = 1e5 + 5;
bool check(int n, int state, int maxDistance, vector<vector<int>>& nextNodes) {
if (__builtin_popcount(state) <= 1) return true;
vector<vector<int>> dist(n, vector<int>(n, maxLen));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = dist[j][i] = nextNodes[i][j];
}
}
for (int k = 0; k < n; ++k) {
if (!((state>>k)&1)) continue;
for (int i = 0; i < n; ++i) {
if (!((state>>i)&1)) continue;
for (int j = 0; j < n; ++j) {
if (!((state>>j)&1)) continue;
dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
}
}
}
for (int i = 0; i < n; ++i) {
if (!((state>>i)&1)) continue;
for (int j = 0; j < n; ++j) {
if (!((state>>j)&1)) continue;
if (dist[i][j] > maxDistance) return false;
}
}
return true;
}
public:
int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
vector<vector<int>> nextNodes(n, vector<int>(n, maxLen));
for (auto& road: roads) {
int u = road[0], v = road[1], w = road[2];
nextNodes[u][v] = min(nextNodes[u][v], w);
nextNodes[v][u] = min(nextNodes[v][u], w);
}
for (int i = 0; i < n; ++i) {
nextNodes[i][i] = 0;
}
int ret = 0;
for (int state = 0; state < (1 << n); ++state) {
if (check(n, state, maxDistance, nextNodes)) {
++ret;
}
}
return ret;
}
};
// 2 << 10 = 1024