# 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';}`