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


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