Click here to Skip to main content
15,745,574 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
Airport Connectivity

In a country, X number of airports exist. There are X-1 direct flights flying among these cities and their flying time is given. It is known that all the airports are connected in a network form based on these given flights. Airport authority find out that the current flying network is not optimal and they want to improve the flight connectivity by reducing time of connectivity. So, they start experimenting with P number of pairs.

For the P pairs, they will provide new direct flight and their flying time. If these two airports are directly connected using the new flight and some old flight path is removed from the network, you have to check if the network become better or not. A network is better if the sum of all the flying time is lesser in the new network than the old one and the network is still connected.

Input format

The first line contains an integer X denoting total numbers of airport.

Each of the next X-1 line contains a triplet (a, b t) which, states that the airport a is connected with airport b in t time. Here a is not equal to b.

Each of the next P lines contains three integers a,b,t which states that the new direct flight from a to b will take t unit of time. Here, all P queries are independent. For each of the P cases, old network is the initial given network.

Output format

For each query you need to print YES if you can improve the network by adding new flight, else print NO.



1 2 2

1 3 3

3 4 5

3 5 4


1 4 4

4 5 6





If we remove the link 3 -> 4 and add the new link 1 -> 4, the time is reduced by 1 unit. First the total was (2+3+5+4)=14, now it will be (2+3+4+4)=13.
For the second query, we can't add the new link because it will increase the time. First the total was (2+3+5+4)=14. Now it will become (2+3+5+6)=16

What I have tried:

using namespace std;

class ProblemSolution{
       int solution(int N);

int ProblemSolution :: solution(int N)
    //write your code here

//Your program will be evaluated by this main method and several test cases.
int main()
    int N;
    cin >> N;
    ProblemSolution problemSolution;
    cout << problemSolution.solution(N);
Updated 7-May-21 7:05am

You need to do what it says in the comment on line 12.
Share this answer
CHill60 7-May-21 12:06pm    
I've just frightened the neighbours by laughing out loud. 5'd!
Richard MacCutchan 7-May-21 12:19pm    
The frustration of all these homework questions is beginning to tell. I am trying not to be rude, but it really gets difficult sometimes. I wonder how many teachers actually explain to their pupils that they need to do their own work?
CHill60 7-May-21 12:12pm    
No. We do not do your homework for you. The point of homework is to benefit you
Richard MacCutchan 7-May-21 12:17pm    
Yes, I could do it for you, but I will not because:
- this assignment is designed to test your understanding of what you have been taught. 
- if I give you the code and you hand it in there could be one of two results:
  - the teacher commends you for a job well done (if my code works).
  - the teacher tells you that you learned nothing (because my code is rubbish).
    but either way it does not test you.
Dave Kreskowiak 7-May-21 12:27pm    
Even better, the teacher sees the code style has vastly changed from previous projects that were turned in and suspects a cheater. He searches the web for the code that was turned in and finds it here. Student then get a failing grade at the least and an expulsion at worst (or best depending on your point of view.)
That is the Travelling salesman problem which you need to understand to write some solving code.
Learn coding with some C++ tutorial to fulfill your assigment. Learn to use the Debugger to see what your code is really doing.
Share this answer

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