.

Return the tour cost and the tour (optional). The triangle inequality guarantees that replacing repeated visits in the full Euler walk by direct edges does not increase cost.

Edge cases and checks:

If n == 1 return cost 0 and tour [0].
If MST is not spanning (some vertex unreachable) return INF/indicate impossibility.
Use long long/large sentinel when summing weights to avoid overflow.

Code

[{"language":"C++","code":"class Solution {\npublic:\n  // dist: n x n matrix (complete graph). Returns tour cost (approx) or large INF if impossible.\n  long long tsp_approx(vector<vector<int>>& dist) {\n    int n = dist.size();\n    if (n == 1) return 0;\n    const long long INF = 9e18;\n    // Prim's algorithm (dense version) to build MST parent array\n    vector<int> parent(n, -1);\n    vector<long long> key(n, INF);\n    vector<char> inMST(n, 0);\n    key[0] = 0; parent[0] = -1;\n    for (int count = 0; count < n; ++count) {\n      int u = -1;\n      long long best = INF;\n      for (int v = 0; v < n; ++v) if (!inMST[v] && key[v] < best) { best = key[v]; u = v; }\n      if (u == -1) return INF; // disconnected\n      inMST[u] = 1;\n      for (int v = 0; v < n; ++v) if (!inMST[v]) {\n        long long w = dist[u][v];\n        if (w < key[v]) { key[v] = w; parent[v] = u; }\n      }\n    }\n\n    // build adjacency list for MST\n    vector<vector<int>> adj(n);\n    for (int v = 1; v < n; ++v) {\n      int p = parent[v];\n      if (p >= 0) { adj[p].push_back(v); adj[v].push_back(p); }\n    }\n\n    // preorder traversal (stack iterative)\n    vector<int> order; order.reserve(n);\n    vector<int> st; st.push_back(0);\n    vector<int> it(n, 0);\n    vector<char> vis(n, 0);\n    while (!st.empty()) {\n      int u = st.back(); st.pop_back();\n      if (vis[u]) continue;\n      vis[u] = 1; order.push_back(u);\n      // push neighbors in reverse to get a deterministic preorder\n      for (int i = (int)adj[u].size()-1; i >= 0; --i) {\n        int v = adj[u][i]; if (!vis[v]) st.push_back(v);\n      }\n    }\n\n    if ((int)order.size() != n) return INF; // not spanning\n\n    long long ans = 0;\n    for (int i = 0; i < n-1; ++i) ans += dist[order[i]][order[i+1]];\n    ans += dist[order.back()][0];\n    return ans;\n  }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--sh

Related Tags

Continue Practicing