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.
SAMPLE INPUT
5
1 2 2
1 3 3
3 4 5
3 5 4
2
1 4 4
4 5 6
SAMPLE OUTPUT
YES
NO
Explanation
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:
#include<iostream>
#include<cstdio>
using namespace std;
class ProblemSolution{
public:
int solution(int N);
};
int ProblemSolution :: solution(int N)
{
}
int main()
{
int N;
cin >> N;
ProblemSolution problemSolution;
cout << problemSolution.solution(N);
}