HackerEarth The new traveling salesman problem solution

In this HackerEarth The new traveling salesman problem solution Alice entered a country that contains n cities and she wants to see all of the cities by incurring the minimum cost possible. There are m two-way roads in the country. A road connects two cities and it has a cost. The ith road connects cities vi, ui and costs ci. The difference between this problem and the classic TSP problem is that switching from a road to another road has a cost.

The viscosity for each road is defined as the ith road having viscosity gi. Switching from a road with viscosity x to a road with viscosity y adds underroot(x*x + y*y) cost. Find the minimum cost needed to see all of the cities.

HackerEarth The new traveling salesman problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N], ans;
int v[MAX_N], u[MAX_N];
bool mark[MAX_N];

void dfs(int c = 0) {
    mark[c] = true;
    for (auto i : g[c]) {
        int o = v[i] ^u[i] ^c;
        if (!mark[o]) {
            ans.push_back(i);
            dfs(o);
            ans.push_back(i);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int w, gl;
        cin >> v[i] >> u[i] >> w >> gl;
        --v[i];
        --u[i];
        g[v[i]].push_back(i);
        g[u[i]].push_back(i);
    }
    dfs();
    assert(ans.size() == n * 2 - 2);
    cout << ans.size() << '\n';
    for (auto i : ans)
        cout << i + 1 << ' ';
    cout << '\n';
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N], ans;
int v[MAX_N], u[MAX_N];
bool mark[MAX_N];

void dfs(int c = 0) {
    mark[c] = true;
    for (auto i : g[c]) {
        int o = v[i] ^u[i] ^c;
        if (!mark[o]) {
            ans.push_back(i);
            dfs(o);
            ans.push_back(i);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int w, gl;
        cin >> v[i] >> u[i] >> w >> gl;
        --v[i];
        --u[i];
        g[v[i]].push_back(i);
        g[u[i]].push_back(i);
    }
    dfs();
    assert(ans.size() == n * 2 - 2);
    cout << ans.size() << '\n';
    for (auto i : ans)
        cout << i + 1 << ' ';
    cout << '\n';
}