PROBLEM LINK: G for Graph | CodeChef
Problem Code: G for Graph | CodeChef
Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef
Contest : Carnival Finale Coding Competition | CodeChef
Author: Codechef Adgitm Chapter : tannatsri | CodeChef User Profile for Tanishq Srivastava | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
DIFFICULTY:
Medium
PROBLEM:
The Chef and his programmer friend are planning to go out on holidays. They have prepared a list of 4 places to visit.
With the help of google maps, Chef’s friend has written the distance between the places where they are going to visit. It is a list of length m where each row consists of the starting point, destination and the distance between the two places.
We can also interpret it as 2 denotes the starting point and 1 denotes the destination and 3 units is the distance between them.
There exists one direct path between every pair of city. Chef’s friend wants to check his programming skills. He tries to find such a path, so they have to travel a minimum distance to visit all the places and return back to the starting point. (They visit every place only once.)
EXPLANATION:
Use comparison.
SOLUTION:
C++:
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m; cin>>m;
int onetotwo = 99999999;
int onetothree = 99999999;
int onetofour = 99999999;
int twotothree = 99999999;
int twotofour = 99999999;
int threetofour = 99999999;
for(int i=0;i<m;i++)
{
int a,b,c; cin>>a>>b>>c;
if((a==1&&b==2)||(a==2&&b==1))
{
onetotwo=min(c,onetotwo);
}
if((a==2&&b==3)||(a==3&&b==2))
{
twotothree=min(c,twotothree);
}
if((a==2&&b==4)||(a==4&&b==2))
{
twotofour=min(c,twotofour);
}
if((a==3&&b==4)||(a==4&&b==3))
{
threetofour=min(c,threetofour);
}
if((a==1&&b==3)||(a==3&&b==1))
{
onetothree=min(c,onetothree);
}
if((a==1&&b==4)||(a==4&&b==1))
{
onetofour=min(c,onetofour);
}
}
int ans=0;
ans=min((onetotwo+twotothree+threetofour+onetofour)
,(onetotwo+twotofour+threetofour+onetothree));
ans=min((onetothree+twotothree+twotofour+onetofour),ans);
ans=min((onetothree+threetofour+twotofour+onetotwo),ans);
cout<<ans<<endl;
}