Road Network
The state Departent of transportation of Rajasthan is thinking of adding a new section of highway to the Highway system. Each highway is connecting 2 cities. Multiple proposals have been submitted by the city officials, each proposal states the pair of cities which will be connected and length of new highway.
Your task is to write program which takes the existing highway system (specified as a set of roads between pair of cities and proposed highway which produces the most improvement in the total travelling distance.
The total travelling distance is the sum of the shortest path distances between pairs of cities.
All highways allow travelling in both directions and the original road network is connected
INPUT:
First line contains 3 positive integers N, H, P, (here N - number of cities, H number of highways in original network, P - number of proposals submitted)
Next H lines contains 3 integers each C1, C2, X representing a highway (here C1, C2 represents the connected cities and X represents the length of highway)
Next P lines contain 3 integers each C1, C2, X representing a proposed highway.
OUTPUT:
one line containing 3 integers C1, C2, X representing the picked proposal (same as it was added in the input)
constraints:
1<=N<=10^2
1<=H<=10^3
1<=P<=10^3
1<=X<=10^5
SAMPLE TESTCASE 0:
input
3 2 2
0 1 10
1 2 10
0 2 1
0 2 2
output
0 2 1
Explanation
Total travelling distance with first proposal: 21
Total travelling distance with second proposal: 22
Hence the best proposal is the first one, hence answer is "0 2 1"
SAMPLE TESTCASE 1:
6 9 3
0 1 2720
1 2 3842
2 3 113
3 4 2418
4 5 7213
3 0 4965
0 5 3848
1 5 9469
2 5 8578
4 0 37
4 2 25
3 1 6
output
4 0 37
Explanation
Adding the proposed highway between cities 0 and 4 with distance 37 produces the smallest sum of all shortest path distances between the cities. thus this is the right answer.
#include <bits/stdc++.h>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,h,p;
cin >> n >> h >> p;
vector<vector<int> > roadmap(n, vector<int>(n, INT_MAX));
for(int i=0;i<h;i++){
int a,b,c;
cin >> a >> b >> c;
roadmap[a][b] = c;
roadmap[b][a] = c;
}
vector<vector<int> > distances(n, vector<int>(n, INT_MAX));
vector<vector<int>> proposals(p, vector<int>(3));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
distances[i][j] = roadmap[i][j];
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if (distances[i][k] != INT_MAX && distances[k][j] != INT_MAX && distances[i][j] > (distances[i][k] + distances[k][j])){
distances[i][j] = distances[i][k] + distances[k][j];
}
}
}
}
for(int i=0;i<p;i++){
cin >> proposals[i][0] >> proposals[i][1] >> proposals[i][2];
}
long total_traveldistance = 0;
for(int i=0;i<roadmap.size();i++){
for(int j=i+1;j<roadmap[0].size();j++){
total_traveldistance += distances[i][j] != INT_MAX ? distances[i][j] : 0;
}
}
vector<pair<int, long> > possibleProposals;
for(int i=0;i<p;i++){
int a = proposals[i][0];
int b = proposals[i][1];
int prev_value = roadmap[a][b];
roadmap[a][b] = proposals[i][2];
roadmap[b][a] = proposals[i][2];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
distances[i][j] = roadmap[i][j];
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if (distances[i][k] != INT_MAX && distances[k][j] != INT_MAX && distances[i][j] > (distances[i][k] + distances[k][j])){
distances[i][j] = distances[i][k] + distances[k][j];
}
}
}
}
long current_traveldistance = 0;
for(int i=0;i<roadmap.size();i++){
for(int j=i+1;j<roadmap[0].size();j++){
current_traveldistance += distances[i][j] != INT_MAX ? distances[i][j] : 0;
}
}
if (current_traveldistance < total_traveldistance){
//cout << proposals[i][0] <<" "<< proposals[i][1] << " " << proposals[i][2]<<endl;
possibleProposals.push_back({i, current_traveldistance});
//break;
}
//restore values....
roadmap[a][b] = prev_value;
roadmap[b][a] = prev_value;
}
long bestpossbiledistance = possibleProposals.size() > 0 ? possibleProposals[0].second : -1;
int bestpossibleindex = 0;
for (int i=1;i<possibleProposals.size();i++){
if (possibleProposals[i].second < bestpossbiledistance){
bestpossbiledistance = possibleProposals[i].second;
bestpossibleindex = possibleProposals[i].first;
}
}
cout << proposals[bestpossibleindex][0] <<" "<< proposals[bestpossibleindex][1] << " " << proposals[bestpossibleindex][2]<<endl;
return 0;
}