Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Saturday, September 7, 2013
Cartman lazy kid finds a shortest path solution (martrix) !!
Question :
Cartman is a very lazy kid. He wants to minimize his walking as much as he can. He has the list of all the cities in south park and also the list of all the roads in there. Every road is identified by the pair of cities it connects and its length. Now cartman asked you what is the shortest distance to go from city "A" to city "B", please help him. If there are "N" cities in south park, they will be numbered as 0, 1, 2 ... N-1.
Cartman is a very lazy kid. He wants to minimize his walking as much as he can. He has the list of all the cities in south park and also the list of all the roads in there. Every road is identified by the pair of cities it connects and its length. Now cartman asked you what is the shortest distance to go from city "A" to city "B", please help him. If there are "N" cities in south park, they will be numbered as 0, 1, 2 ... N-1.
Inputs :
The first line will contain two integers "N" the no. of cities and "R" the no. of roads connecting them. Each of the next "R" lines has three integers "X Y L" which means that city "X" and city "Y" are connected by a road of length "L". The next line contains an integer "Q", the no. of queries asked by Cartman. Each of the next "Q" lines contains two integers "A B" denoting a pair of cities queried by Cartman.
The first line will contain two integers "N" the no. of cities and "R" the no. of roads connecting them. Each of the next "R" lines has three integers "X Y L" which means that city "X" and city "Y" are connected by a road of length "L". The next line contains an integer "Q", the no. of queries asked by Cartman. Each of the next "Q" lines contains two integers "A B" denoting a pair of cities queried by Cartman.
Outputs :
For each query "Q" you have to tell him the lenght of the shortest path to reach from "A" to "B" in a different line. It is guaranteed that there will be a path from every city to every other city.
For each query "Q" you have to tell him the lenght of the shortest path to reach from "A" to "B" in a different line. It is guaranteed that there will be a path from every city to every other city.
Constraints :
1 <= N <= 100, 1 <= R <= N*(N-1)/2, 0 <= X,Y <= N-1, 1 <= L <= 1000, 1 <= Q <= 1000, 0 <= A,B <= N-1,
1 <= N <= 100, 1 <= R <= N*(N-1)/2, 0 <= X,Y <= N-1, 1 <= L <= 1000, 1 <= Q <= 1000, 0 <= A,B <= N-1,
Level : Medium
Solution to the Problem :
#include<iostream>
using namespace std;
long long int min(long long int i,long long int j)
{
if(i<j)
return i;
return j;
}
main()
{
long long int n;
scanf("%lld",&n);
long long int arr[n][n];
long long int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
arr[i][j]=100000000;
}
long long int r;
scanf("%lld",&r);
while(r--)
{
long long int x,y,l;
scanf("%lld%lld%lld",&x,&y,&l);
arr[x][y]=arr[y][x]=l;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
arr[j][k]=min(arr[j][k],arr[j][i]+arr[i][k]);
}
}
long long int mm;
scanf("%lld",&mm);
while(mm--)
{
long long int ll,kk;
scanf("%lld%lld",&ll,&kk);
printf("%lld\n",arr[ll][kk]);
}
}
