We consider an undirected graph with (n) nodes and (m) weighted edges. The task is to select edges that connect all nodes in a tree-like fashion, but the cost rule differs from a standard minimum spanning tree. When an edge with weight (w) is added between a node already placed at depth (d) and a newly visited node, the incurred cost is (d \times w). The root starts at depth 1 and only edges incident to visited nodes may be activated. The objective is to minimize the total cost.

Two approaches are discussed. The first uses a greedy heuristic during DFS and fails on some corner cases. The second uses state compression to prune the search effectively.

Greedy DFS (Flawed)

A naive depth-first search enumerates orders of adding nodes. At each step the algorithm extends the current connected set by scanning all visited nodes and choosing unvisited neighbors with the smallest possible cost. Although the search backtracks, a greedy filter sum + (dep[vis[i]]+1)*l[j] > ans discards states too aggressively. Moreover, reusing a state-cost array s[] that only improves when a lower total is found does not capture sufficient information, leading to wrong answers on specific inputs.

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
const int MAXN = 1000, MAXM = 4000;
int hd[MAXM], nxt[MAXM], to[MAXM], weight[MAXM];
int visited[MAXN], inPath[MAXN], level[MAXN], idx[MAXN];
long long stateCost[1 << 13];
int n, m, edgeCnt, pathLen;
long long best = INF;

void addEdge(int u, int v, int w) {
    nxt[++edgeCnt] = hd[u]; hd[u] = edgeCnt; to[edgeCnt] = v; weight[edgeCnt] = w;
    nxt[++edgeCnt] = hd[v]; hd[v] = edgeCnt; to[edgeCnt] = u; weight[edgeCnt] = w;
}

void dfs(int chosen, long long curCost, int mask) {
    if (curCost >= best) return;
    if (chosen == n) {
        best = min(best, curCost);
        return;
    }
    for (int i = 1; i <= pathLen; ++i) {
        int u = inPath[i];
        for (int e = hd[u]; e; e = nxt[e]) {
            int v = to[e];
            long long add = (level[u] + 1) * weight[e];
            if (curCost + add >= best) continue;
            int nxtMask = mask | (1 << v);
            if (!visited[v] && stateCost[nxtMask] > curCost + add) {
                visited[v] = 1;
                inPath[++pathLen] = v;
                level[v] = level[u] + 1;
                stateCost[nxtMask] = curCost + add;
                dfs(chosen + 1, curCost + add, nxtMask);
                --pathLen;
                level[v] = 0;
                visited[v] = 0;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        if (u != v) addEdge(u, v, w);
    }
    for (int root = 1; root <= n; ++root) {
        fill(stateCost, stateCost + (1 << (n + 1)), INF);
        pathLen = 1;
        inPath[pathLen] = root;
        visited[root] = 1;
        dfs(1, 0, 1 << root);
        visited[root] = 0;
    }
    printf("%lld\n", best);
    return 0;
}

State Compression + DFS (Full Score)

The robust solution treats the state as a bitmask of visited nodes and uses an array path to hold the current exploration sequence. For each node, adjacent edges are sorted by weight so that cheaper extensions are tried first. The DFS proceeds from a given node and attempts to attach each unvisited neighbor of every node already in the path. Global accumulators keep track of the current total cost and the sum of the smallest edge from each unvisited node (used as a lower bound to prune hopeless branches).

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e16;
const int MAXN = 1100;
int edgeCost[MAXN][MAXN];
int adj[MAXN][MAXN], deg[MAXN];
int path[MAXN], level[MAXN];
long long ans = INF, curTotal, minEdgeSum;
int n, m, pathEnd;

void sortAdj(int l, int r, int node) {
    int i = l, j = r, pivot = edgeCost[node][adj[node][(l + r) / 2 + 1]];
    while (i <= j) {
        while (edgeCost[node][adj[node][i]] < pivot) ++i;
        while (edgeCost[node][adj[node][j]] > pivot) --j;
        if (i <= j) {
            swap(adj[node][i], adj[node][j]);
            ++i; --j;
        }
    }
    if (l < j) sortAdj(l, j, node);
    if (i < r) sortAdj(i, r, node);
}

void search(int startIdx, int attemptFrom) {
    for (int i = startIdx; i <= pathEnd; ++i) {
        if (curTotal + minEdgeSum * level[path[i]] >= ans) return;
        for (int j = attemptFrom; j <= deg[path[i]]; ++j) {
            int v = adj[path[i]][j];
            if (!level[v]) {
                ++pathEnd;
                path[pathEnd] = v;
                minEdgeSum -= edgeCost[v][adj[v][1]];
                curTotal += edgeCost[path[i]][v] * level[path[i]];
                level[v] = level[path[i]] + 1;
                search(i, j + 1);
                level[v] = 0;
                curTotal -= edgeCost[path[i]][v] * level[path[i]];
                minEdgeSum += edgeCost[v][adj[v][1]];
                --pathEnd;
            }
        }
        attemptFrom = 1;
    }
    if (pathEnd == n) {
        if (curTotal < ans) ans = curTotal;
        return;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            edgeCost[i][j] = INF;
    for (int i = 0; i < m; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        if (edgeCost[u][v] < w) continue;
        if (edgeCost[u][v] == INF) {
            adj[u][++deg[u]] = v;
            adj[v][++deg[v]] = u;
        }
        edgeCost[u][v] = edgeCost[v][u] = w;
    }
    for (int i = 1; i <= n; ++i) {
        sortAdj(1, deg[i], i);
        minEdgeSum += edgeCost[i][adj[i][1]];
    }
    for (int r = 1; r <= n; ++r) {
        curTotal = 0;
        pathEnd = 1;
        path[1] = r;
        minEdgeSum -= edgeCost[r][adj[r][1]];
        level[r] = 1;
        search(1, 1);
        level[r] = 0;
        minEdgeSum += edgeCost[r][adj[r][1]];
    }
    printf("%lld\n", ans);
    return 0;
}

The ordering of neighbors by edge weight guarantees that promising extensions are explored early. The precomputed minEdgeSum provides an admissible heuristic: even if all remaining nodes could be attached using their cheapest incident edge, the additional cost is atleast the sum of those minima multiplied by the respective depths. When curTotal + minEdgeSum * depth exceeds the best answer so far, the branch is cut off.