SPIBIKER Editorial

editorial
,
1

Problem Code: SPIBIKER(CodeChef: Practical coding for everyone)
Setter : Shivam Gupta
Editorialist : Shivam Gupta

DIFFICULTY: Hard

Problem

Spider-Man is travelling from Delhi to Ladakh. He plans to visit all the N

tourist spots between Delhi and Ladakh (both included). These tourist spots are connected to one another (directly or via some other spots) and have different distances.

Spider-Man has data of all the connecting routes, i.e., he knows the distance D

from spot X to Y. Delhi is numbered as spot 1 and Ladakh is numbered as spot N. As Spider-Man is in a hurry, so he wants to reach the final destination Ladakh by travelling the minimum possible distance and also make sure to visit all the tourist spots. Can you help him in doing do?

Quick Explaination

  • Initialise minSum to INT_MAX.
  • Traverse the graph from the source node S using BFS.
  • Mark each neighbouring node of the source as the new source and perform BFS from that node.
  • Once the destination node D is encountered, then check if all the nodes are visited or not.
  • If all the nodes are visited, then update the minSum and return the minimum value.
  • If all the nodes are not visited, then return minSum.
  • Mark the source as unvisited.
  • Check the remaining nodes which are not in the path of minimum sum.
  • Now,find the nearest node of remaining nodes from the path of minSum’s node and add twice the distance of it.

Solution

#include <bits/stdc++.h>
using namespace std;

int minSum = INT_MAX;
vector<bool> visi;
unordered_set<int> mp;
int counts = 0;
int finalMinSum = INT_MAX;

void getMinPathSum(unordered_map<int,
								 vector<pair<int,
											 int>>> &graph,
				   vector<bool> &visited,
				   int src, int dest, int currSum)
{

	if (src == dest)
	{

		bool flag = true;
		if (flag)
		{

				visi.clear();
				mp.clear();
				counts = 0;
				for (int i = 0; i < visited.size(); i++)
				{
					visi.push_back(visited[i]);
				}
				for (int i = 0; i < visi.size(); i++)
				{
					if (visi[i])
					{
						mp.insert(i);
						counts++;
					}
				}
				while (counts < visi.size())
				{
					int minWeight = INT16_MAX;
					int a = 0, b = 0;
					for (auto it = graph.begin(); it != graph.end(); it++)
					{
						for (int i = 0; i < it->second.size(); i++)
						{
							if (int(mp.find(it->first) == mp.end()) + int(mp.find(it->second[i].first) == mp.end()) == 1)
							{
								if (it->second[i].second < minWeight)
								{
									a = it->first;
									b = it->second[i].first;
									minWeight = it->second[i].second;
								}
							}
						}
					}
					mp.insert(a);
					mp.insert(b);
					counts++;
					currSum += 2 * minWeight;
				}

			if (finalMinSum > currSum)
			{
				finalMinSum=min(finalMinSum,currSum);
			}
		}
		return;
	}
	else
	{

		visited[src] = true;

		for (auto node : graph[src])
		{

			if (!visited[node.first])
			{

				visited[node.first] = true;

				getMinPathSum(graph, visited, node.first,
							  dest, currSum + node.second);

				visited[node.first] = false;
			}
		}

		visited[src] = false;
	}
}

int main()
{
	unordered_map<int, vector<pair<int,
								   int>>>

		graph;

	int n,m;
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		vector<pair<int,int>> vect;
		graph[i] = vect;
	}
	int a,b,weight;
	while(m--)
	{
		cin>>a>>b>>weight;
		graph.find(a-1)->second.push_back(make_pair(b-1,weight));
		graph.find(b-1)->second.push_back(make_pair(a-1,weight));
	}

	int source = 0;

	int dest = n-1;

	vector<bool> visited(n, false);
	getMinPathSum(graph, visited,source, dest, 0);

	if (finalMinSum == INT_MAX)
		cout << "-1\n";
	else
		cout << finalMinSum << '\n';
	return 0;
}
2

Is This TSP(Traveling Salesman Problem)?

1 Like