Click here to Skip to main content
15,868,016 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
So i am stuck on this Imperial Messenger challenge , i'm sorry for this big copy paste in advance : 

Input
The input will describe the routes between the n cities. All cities are reachable using some path from the capitol city. The first line of the input will be n, the number of cities, such that 1 <= n <= 100. The rest of the input defines an adjacency matrix, A. The adjacency matrix is square and of size n×n. Each of its entries will be either an integer or the character x. The value of A(i, j) indicates the time required to travel from city i to city j. A value of x for A(i, j) indicates that a message cannot be sent directly from city i to city j.

Note that for a city to send a message to itself does not require a messenger, so A(i, i) = 0 for 1 <= i <= n. Also, you may assume that the adjacency matrix is undirected (messengers can travel in either direction in equal time), so that A(i, j) = A(j, i). Thus only the entries on the (strictly) lower triangular portion of A will be supplied as input. The input to your program will be the lower triangular section of A. That is, the second line of input will contain one entry, A(2, 1). The next line will contain two entries, A(3, 1) and A(3, 2), and so on.

Output
Your program should output the minimum time required before a message sent from the capitol (city #1) is known throughout the empire, i.e. the time it is received in the last city to get the message.

Sample Input
5
50
30 5
100 20 50
10 x x 10

Output for the Sample Input
35


What I have tried:

so essentially , i got the main part actually(2d array with input etc..) but the main issue that i am facing is calculating the output, i recently started learning c++ couple weeks ago.

I tried calculating all of the input together then divide them by the amount of elements without success + a bunch of other things, been working on this for a while at this point and i really don't know what to try anymore !

thank you very much !

#include <iostream>
using namespace std;

class Matrix
{
public:	
	int GetRows() 
	{
		return rows;
	}
	int GetColumns() 
	{
		return columns;
	}
	void SetMatrixSize(int size) 
	{
		rows = size;
		columns = size;
	}
	void SetNumberOfRows(int rowAmount) 
	{
	rows = rowAmount;
	}
	void SetNumberOfColumns(int columnAmount) 
	{
		columns = columnAmount;
	}

private:
	unsigned int rows;
	unsigned int columns;
};

int main()
{
	Matrix obj;
	int amountOfCity;
	

	std::cout << "Enter the amount of city : " << endl;
	cin >> amountOfCity;

	//Clamping Number Of City
	if (amountOfCity < 1) 
	{
		amountOfCity = 1;
		std::cout<< "Cannot have less than one city !"<<endl;
	}
	if (amountOfCity > 100) 
	{
		amountOfCity = 100;
		std::cout<< "Cannot have more than 100 cities ! " << endl;
	}


	obj.SetMatrixSize(amountOfCity -1);



	//Allocating memory
	int** matrix = new int* [obj.GetRows()];

	for (unsigned int i = 0; i < obj.GetRows(); i++)
	{
		matrix[i] = new int[obj.GetColumns()];
	}

	int iteration = 0;

	//Set Value for element in the matrix with user input
	for (int x = 0; x < obj.GetRows(); x++) 
	{
		for (int y = 0; y < obj.GetColumns(); y++) 
		{
			//Initialize to 0
			matrix[x][y] = 0;
			int value = 0;

			if (y <= iteration)
			{
				std::cout << "Enter the values : " << endl;
				cin >> value;
				
				matrix[x][y] = value;
			}

			if (y == obj.GetColumns() -1) 
			{
				iteration++;
			}			
		}
	}

	//Displaying the matrix
	std::cout << "Here is your matrix : " << endl;
	for (int x = 0; x < obj.GetRows(); x++)  
	{
		for (int y = 0; y < obj.GetColumns(); y++)  
		{
			std::cout <<" "<<matrix[x][y];
		}
		std::cout << endl;
	}


	
	//Time calculation

	
	for (int x = 0; x < obj.GetRows(); x++) 
	{
		for (int y = 0; y < obj.GetColumns(); y++) 
		{
			if (matrix[x][y] == 0) //ignore if value is 0
			{
				continue;
			}
			
            //Here would be where i am stuck essentially  
			
		}
	}


	//Deallocate the memory after using it
	for (unsigned int i = 0; i < obj.GetRows(); i++)
	{
		delete[] matrix[i];
	}
	delete[] matrix;

	cin.ignore();
	cin.get();
	
	return 0;
}
Posted
Updated 12-Oct-22 4:57am
v2

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 
Comments
Sohkar A Lensky 7-Oct-22 10:15am    
well my bad ive never written on code forums and stuff , at the moment i have pretty much everything , the 2d array , triangular matrix etc like i wrote i am only stuck at the end , the calculation to get the requested output : 35 based on my matrix just this little part , not the whole challenge of course, so yeah thats my next step , i tried adding everything then dividing , didnt work , i tried getting all of the smallest numbers together , couldnt filter through the array. so yeah thats where i am mainly
Sohkar A Lensky 7-Oct-22 10:16am    
i thought showing the whole thing would help people understand what was happening x)
Greg Utas 7-Oct-22 10:20am    
You need to show your existing code, not just the problem statement. Without it, people will assume that you may have done nothing, because we get "write this code from scratch" questions all the time.
Greg Utas 7-Oct-22 10:32am    
Sorry to be a pain, but you should edit your question and append the code there.
Sohkar A Lensky 7-Oct-22 10:44am    
is it okay like this ? sorry first time user on this website
As I understand the problem it reduces to creating all the permutations of the numbers [0, N]. This as you know is a common algorithm which in case you do not know is in fact provided by the Standard Template Library link below. Scroll down to "Permutation operations". If I am mistaken I would appreciate being informed. Thank You Kindly
https://en.cppreference.com/w/cpp/algorithm[^]
 
Share this answer
 
Comments
Sohkar A Lensky 12-Oct-22 11:33am    
Yeah it makes sense, since im kindda new to c++ i wasnt aware of these. Thank you very much for working on this

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900