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