Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth The new traveling salesman problem solution

YASH PAL, 31 July 202431 July 2024
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';
}
coding problems

Post navigation

Previous post
Next post
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
  • Hackerrank Day 14 scope 30 days of code solution
©2025 Programmingoneonone | WordPress Theme by SuperbThemes