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
Tuesday, September 10, 2013
Graphs and Types of graphs
Graphs – An Introduction
A graph is an ordered triple (V(G),E(G),ψG).Where graph G consists of-
V(G) – a non-empty set of vertices,
E(G) – a set of edges (it can be null i.e. a Null set )
ψG – a incident function that associates with each edge
of graph G in an unordered pair vertices of G.
If e is an edge and u and v are its vertices such that ψ0(e)=uv then e is are said to be joined.
The vertices u and v are said to be the ends of the edge e .
Consider the given example –
 |
| A graph |
In this the graph G consists of five vertices i.e. V(G) = {A,B,C,D,E} and four edges namely E(G) = { (A,B),(A,C),(A,D),(A,E) }
and hence for the graph G the incidence function ψG is given as –
ψe(A,B) = AB
ψe(A,C) = AC
ψe(A,D) = AD
ψe(A,E) = AE
Planar Graphs – The graphs that have a diagram whose edges intersect only at their ends, in simple
words they are graph that can be represented in a plane.
Some points to be remembered –
The ends of an edge are incident with the edge and the edge is incident on the ends.
Two vertices are said to be incident if they have acommon edge i.e. those vertices are end points of the edge.
Two edges are said to be incident if they have common vertice.
An edge with same ends points i.e. which points to one vertex is called loop.
An edge with different ends is called as a link.
Symbols used in Graph theory –
G - Graph
V - Vertices set
E - Edges set
| V | - Total number of vertices in graph G.
| E | - Total number of edges in graph G.
δ(G) – Minimal degree of all vertices in graph G
Δ (G) - Maximum degree of all vertices in graph G
Types of Graphs
There are different types of graphs based on their direction, links and loops (I hope u know what these terms are ) .
They can be discussed below as –
Directed graph / Digraph :
A graph containing arrows as a link is called a directed graph or a digraph.
 |
| Directed graph |
 |
| Non -Directed Graph |
 |
| Mixed Graph |
Self-loop graph : A graph with loops (i.e. joining itself) is called self loop graphs.
 |
| Self-loop Graph |
Multi graph : A graph containing loops and parallel edges in it is called a multi graph.
 |
| Multi Graph |
 |
| Simple Graph |
Finite graph : A graph with finite number of edges is called a finite graph.
 |
| Finite Graph |
Infinite graph : A graph with infinite number of edges is called infinite graph.
e.g. Considering universe stars as vertices, can u join all stars ?
Answer is no because they are in infinite numbers same goes here, where universe in infinite graph.
Trivial graph : A graph having only one vertex but no edge is called a trivial graph.
 |
| Single vertex : Trivial Graph |
 |
| Null graph |
Pseudo graph : A graph containing loops but no parallel edges is called pseudo graph.
 |
| Pseudo Graph |
Weighted graph :When the edges are assigned with weights on them then such a graph is called a weighted graph.
 |
| Weighted Graph |
Wheel graph : When all the vertices of the graph join to single vertex then it is called a wheel graph.
 |
| Wheel Graph |
| Relations between the above graphs: Every trivial graph is a simple graph but vice versa is not true. |
Every Null graph is a simple graph but vice versa not true.
Except infinite graph above all graphs are finite graphs until it edges can be counted.
In wheel graph all the edges can be accessed by a single vertex i.e. it has a same starting point or say ending point.
Saturday, September 7, 2013
Geeky person Ross does geeky things himself solution...
Question :
SRoss is a geek but he never admits it. He plays weird geeky games and enjoys them a lot. Recently he started playing a new game. He takes an array of "N" integers. Then he makes another array out of it which contains the sum of all the contiguous sub arrays of the original array. He sorts them is non-increasing order and keeps them in an array S that has 1-based index. Now he wants the find the elements at position K1, K2 and K3 in it.
For ex. if the array has 3 elements {10, 20, 30}, then the formed array will have 6 elements as S[1..6] = { 60, 50, 30, 30, 20, 10 }
SRoss is a geek but he never admits it. He plays weird geeky games and enjoys them a lot. Recently he started playing a new game. He takes an array of "N" integers. Then he makes another array out of it which contains the sum of all the contiguous sub arrays of the original array. He sorts them is non-increasing order and keeps them in an array S that has 1-based index. Now he wants the find the elements at position K1, K2 and K3 in it.
For ex. if the array has 3 elements {10, 20, 30}, then the formed array will have 6 elements as S[1..6] = { 60, 50, 30, 30, 20, 10 }
Inputs :
First line of the input will contain 4 integers "N", "K1", "K2" and "K3". The next line will contain "N" integers A[0], A[1] .. A[N-1].
First line of the input will contain 4 integers "N", "K1", "K2" and "K3". The next line will contain "N" integers A[0], A[1] .. A[N-1].
Outputs :
Output three integers, the elements at position K1, K2 and K3 in the formed array separated by a single space.
Output three integers, the elements at position K1, K2 and K3 in the formed array separated by a single space.
Constraints :
2 <= N <= 10^4, 1 <= K1 <= K2 <= K3 <= 2000, K3 <= N*(N+1)/2, -10^4 <= A[i] <= 10^4
2 <= N <= 10^4, 1 <= K1 <= K2 <= K3 <= 2000, K3 <= N*(N+1)/2, -10^4 <= A[i] <= 10^4
Level :Thinker,admirer
Solution to the Problem :
#include<stdio.h>
#include<limits.h>
#define MAX 4100
#define MAX_TOTAL 10300
class minheap{
public:
minheap()
{
last=1;
a[0]=INT_MIN;
}
void insert(int n)
{
a[last++]=n;
cascadeup(last-1);
}
int top()
{
return a[1];
}
int extractmin()
{
int ans=a[1];
if(size()){
a[1]=a[last-1];
last--;
cascadedown(1);
return ans;
}
else return INT_MIN;
}
int cascadedown(int pos)
{
int key=a[pos];
int child=pos<<1;
while((child<last)){
if(child+1<last)
if(a[child]>a[child+1])
child++;
if(a[child]>key)
break;
else{
a[pos]=a[child];
pos=child;
child<<=1;
}
}
a[pos]=key;
return pos;
}
int cascadeup(int pos)
{
int key=a[pos];
while((pos!=1)&&(key<a[pos/2])){
a[pos]=a[pos/2];
pos>>=1;
}
a[pos]=key;
return pos;
}
int size(){return last-1;}
private:
int last;
int a[MAX+1];
};
int main()
{
int cases,i,n,j,sum;
int k1,k2,k3,heapsize;
int prefix[MAX_TOTAL];
int a[MAX_TOTAL];
int maxsum[MAX];
minheap heap;
scanf("%d",&n);
scanf("%d%d%d",&k1,&k2,&k3);
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
prefix[0]=0;
for(i=1;i<=n;++i) prefix[i]=prefix[i-1]+a[i];
for(heapsize=0,i=0;i<=n;++i)
for(j=i+1;j<=n;++j){
sum=prefix[j]-prefix[i];
if(heapsize<k3){
heap.insert(sum);
heapsize++;
}
else if(sum>heap .top()){
heap. extractmin();
heap .insert(sum);
}
}
for(i=k3;i;--i)
maxsum[i]=heap. extractmin();
printf("%d ",maxsum[k1]);
printf("%d ",maxsum[k2]);
printf("%d\n",maxsum[k3]);
while(1)
{}
}
Changing the word problem's solution
Question :
Joey's Computer got a bug. Whenever there is a word, it changes itself such that all the letters at the even position comes to the beginning of the word. For ex: "computer" will become "optrcmue", "who" will change to "hwo" etc. But he found out that there will be some words, that will remain same even after this change, for ex. "aab" will remain "aab". Now, if we use only lower case english letters, Joey wants to know how many "N" letters words are there that remain same after this change. As the answer can be quite large, print in modulo 1000000007.
Joey's Computer got a bug. Whenever there is a word, it changes itself such that all the letters at the even position comes to the beginning of the word. For ex: "computer" will become "optrcmue", "who" will change to "hwo" etc. But he found out that there will be some words, that will remain same even after this change, for ex. "aab" will remain "aab". Now, if we use only lower case english letters, Joey wants to know how many "N" letters words are there that remain same after this change. As the answer can be quite large, print in modulo 1000000007.
Inputs :
The first line will contain "T", the no. of testcases. Each of the next "T" lines will have an integer "N".
The first line will contain "T", the no. of testcases. Each of the next "T" lines will have an integer "N".
Outputs :
For each test case, print the number of "N" letters words that will remain same after this change modulo 1000000007.
For each test case, print the number of "N" letters words that will remain same after this change modulo 1000000007.
Constraints :
1 <= T <= 100, 1 <= N <= 10^5
1 <= T <= 100, 1 <= N <= 10^5
Level : Medium
Solution to the Problem :
#include<stdio.h>
long long int arr[100000];
void per()
{
arr[0]=1;
long long int i;
for(i=1;i<100000;i++)
arr[i]=(arr[i-1]*26)%1000000007;
}
void perform(long long int *x,long long int fn,long long int sn)
{
if(x[sn]==0)
{
x[sn]=fn;
return;
}
if(x[sn]<fn)
{
long long int t=x[sn];
x[sn]=fn;
perform(x,t,fn);
return;
}
if(x[sn]>fn)
{
perform(x,fn,x[sn]);
return;
}
}
long long int count(long long int *x,long long int n)
{
long long int c=0;
long long int i;
for(i=1;i<=n;i++)
{
if(!x[i])
c++;
}
return c;
}
long long int count(long long int n)
{
long long int x[n+1];
long long int i;
for(i=1;i<=n;i++)
{
x[i]=0;
}
for(i=1;i<=n;i++)
{
long long int fn,sn;
if(i&1)
{
fn=i;
sn=i-i/2+n/2;
}
else
{
fn=i/2;
sn=i;
}
perform(x,fn,sn);
}
printf("%lld\n",arr[count(x,n)+n%2]);
}
main()
{
per();
long long int t;
scanf("%lld",&t);
while(t--)
{
long long int n;
scanf("%lld",&n);
count(n);
}
}
Solution to a differnent XORing Problem
Question :
Let us suppose we have a “N” bit integer X. We call an integer X’ as neighbor-X, if X’ can be obtained by shuffling the bits of integer X.
For ex. If X = 6 and N = 5, then X will be represented as X = (00110)2, So all the 5 bit integers that have exactly two 1s in their binary representation are called neighbor-X. For ex. (00011)2, (01001)2, (10100)2, … all of these are neighbor-X.
Now you are given two N bit integers “X” and “Y”, then you have to find the maximum possible value of (X’ xor Y’) where X’ is neighbor-X.
xor operator takes two bit strings and performs XOR operation between them. For ex:(10010)2 xor (01011)2 =(11001)2
Let us suppose we have a “N” bit integer X. We call an integer X’ as neighbor-X, if X’ can be obtained by shuffling the bits of integer X.
For ex. If X = 6 and N = 5, then X will be represented as X = (00110)2, So all the 5 bit integers that have exactly two 1s in their binary representation are called neighbor-X. For ex. (00011)2, (01001)2, (10100)2, … all of these are neighbor-X.
Now you are given two N bit integers “X” and “Y”, then you have to find the maximum possible value of (X’ xor Y’) where X’ is neighbor-X.
xor operator takes two bit strings and performs XOR operation between them. For ex:(10010)2 xor (01011)2 =(11001)2
Inputs :
The first line of the input will contain an integer “T”, the no. of test cases. Each of the next “T” lines will contain three integers “N”, “X” and “Y”, N is the no. of bits in integers X and Y.
The first line of the input will contain an integer “T”, the no. of test cases. Each of the next “T” lines will contain three integers “N”, “X” and “Y”, N is the no. of bits in integers X and Y.
Outputs :
For each test case you have to print the maximum possible value of (X’ xor Y’) in a separate line.
For each test case you have to print the maximum possible value of (X’ xor Y’) in a separate line.
Constraints :
1 <= T <= 100, 1 <= N <= 10^5
1 <= T <= 100, 1 <= N <= 10^5
Level : Medium
Solution to the Problem :
#include<stdio.h>
int pow(int x,int k)
{
if(k==0)
return 1;
return x*pow(x,k-1);
}
int min(int i,int j)
{
return i<j?i:j;
}
int find(int n)
{
int c=0;
while(n>0)
{
if(n&1)
c++;
n=n>>1;
}
return c;
}
main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
int k=find(a);
int l=find(b);
int res=min(k,n-l)+min(n-k,l);
int kk=n-res;
printf("%d\n",(pow(2,res)-1)<<kk);
}
}
Problem - Pass the time with maximum fun after movie - Solution
Question :
Joey just got free from a shooting and he wants to have a lunch. Director of the movie gave him only "K" units of time for the lunch. There are "N" restaurants in the city. For the ith restuarant, there are two values that Joey knows, "Fi" and "Ti". Ti is the amount of time it would take if Joey eats the lunch in the ith restuarant. If Ti is less than or equal to K, Joey will have Fi amount of fun in that restuarant. If Ti is greater than K, then Joey's fun will be calculated as Fi - (Ti - K).
Joey has the list of all restaurants and Fi and Ti values for all of them. Please tell him the Maximum fun that he can have. He will have his lunch in only one restaurant. The maxiumum can be negative also.
Joey just got free from a shooting and he wants to have a lunch. Director of the movie gave him only "K" units of time for the lunch. There are "N" restaurants in the city. For the ith restuarant, there are two values that Joey knows, "Fi" and "Ti". Ti is the amount of time it would take if Joey eats the lunch in the ith restuarant. If Ti is less than or equal to K, Joey will have Fi amount of fun in that restuarant. If Ti is greater than K, then Joey's fun will be calculated as Fi - (Ti - K).
Joey has the list of all restaurants and Fi and Ti values for all of them. Please tell him the Maximum fun that he can have. He will have his lunch in only one restaurant. The maxiumum can be negative also.
Inputs
First Line will contain two integers N and K. Each of the next N lines will contain two integers Fi and Ti.
First Line will contain two integers N and K. Each of the next N lines will contain two integers Fi and Ti.
Outputs :
Print a single integer that tells the maximum fun that Joey can have.
Print a single integer that tells the maximum fun that Joey can have.
Constraints
1 <= N <= 10^4, 1 <= K <=10^9, 1 <= Fi,Ti <=10^9
1 <= N <= 10^4, 1 <= K <=10^9, 1 <= Fi,Ti <=10^9
Level :Starter,Cakewalk
Solution to the Problem :
#include<stdio.h>
int arr[10001];
void preprocess()
{
arr[1]=10;
int i;
for(i=2;i<=10000;i++)
arr[i]=(arr[i-1]*10)%21;
}
void print(int k)
{
//printf("%d\n",arr[k-2]);
int x=arr[k-2];
printf("1");
int i;
for(i=1;i<=k-4;i++)
printf("0");
if(x==0)
printf("000");
else
{
x=21-x;
if(x<10)
{
printf("0%d0",x);
}
else
{
printf("%d0",x);
}
}
printf("\n");
}
main()
{
preprocess();
int k;
scanf("%d",&k);
if(k==1||k==2)
printf("-1\n");
else if(k==3)
printf("210\n");
else if(k==4)
printf("1050\n");
else
print(k);
}
SPOJ:Cartman stoles the cookies and escapes solution !!
Question :
Cartman went to Stan's home tonight, but Stan's family had to go out immediately due to some important work. They left Cartman at their home and asked him to see the belongings till they come back.
But Cartman's intention's were totally different, as soon as Stan's family left, he entered into their kitchen. He saw that there were "N" cupboards in the kitchen. All of them had cookies in them. Cartman went to each cupboard and ate all the cookies. After eating the cookies he realized that he should not leave any clue behind him that he ate the cookies. Each cupboard had two doors, a left door and a right door. He remembered that when he came there all the left doors were in the same position (open or closed). Also the right doors were also in the same position (open or closed). Cartman realized that he should maintain this condition before the Stan's family arrives. But he didn't remember the initial position of the doors. So, he only tries to make all the left door in the same position and all the right doors in the same position. For example, all the left doors may be open and all the right doors may be closed. Cartman opens or closes a door in one second. He wants to achieve his goal in the minimum time. Write a program that tells the minimum time required to acheive this task.
Cartman went to Stan's home tonight, but Stan's family had to go out immediately due to some important work. They left Cartman at their home and asked him to see the belongings till they come back.
But Cartman's intention's were totally different, as soon as Stan's family left, he entered into their kitchen. He saw that there were "N" cupboards in the kitchen. All of them had cookies in them. Cartman went to each cupboard and ate all the cookies. After eating the cookies he realized that he should not leave any clue behind him that he ate the cookies. Each cupboard had two doors, a left door and a right door. He remembered that when he came there all the left doors were in the same position (open or closed). Also the right doors were also in the same position (open or closed). Cartman realized that he should maintain this condition before the Stan's family arrives. But he didn't remember the initial position of the doors. So, he only tries to make all the left door in the same position and all the right doors in the same position. For example, all the left doors may be open and all the right doors may be closed. Cartman opens or closes a door in one second. He wants to achieve his goal in the minimum time. Write a program that tells the minimum time required to acheive this task.
Inputs :
First line of the input will contain a single integer "N", the no. of cupboards. Each of the next "N" lines contain two integers Li and Ri. Li equals 1 if the left door of the i-th cupboard is open, Li equals 0 if the left door of the i-th cupboard is closed. Similarly Ri is 1 if right door is open and 0 if right door is closed.
First line of the input will contain a single integer "N", the no. of cupboards. Each of the next "N" lines contain two integers Li and Ri. Li equals 1 if the left door of the i-th cupboard is open, Li equals 0 if the left door of the i-th cupboard is closed. Similarly Ri is 1 if right door is open and 0 if right door is closed.
Outputs :
Print a single integer "T", the minimum no. of seconds Cartman needs to change the doors of all cupboards to the position he needs.
Print a single integer "T", the minimum no. of seconds Cartman needs to change the doors of all cupboards to the position he needs.
Constraints :
2 <= N <= 10^4, 0 <= Li, Ri <=1,
2 <= N <= 10^4, 0 <= Li, Ri <=1,
Level : Medium
Solution to the Problem :
#include<stdio.h>
int min(int i,int j)
{
return (i<j)?i:j;
}
main()
{
int n,i;
scanf("%d",&n);
int l[n];
int r[n];
for(i=0;i<n;i++)
scanf("%d%d",&l[i],&r[i]);
int c1,c2;
c1=c2=0;
for(i=0;i<n;i++)
{
if(l[i]==0)
c1++;
if(r[i]==0)
c2++;
}
printf("%d\n",min(c1,n-c1)+min(c2,n-c2));
}
Butter like to solve recurrences SPOJ' problem- Solution O(log n)
Question :
Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:
F(n) = 2*F(n-1) + 3*F(n-2) with F(1)=1 and F(2) =2
So the series becomes:
1 2 7 20 61 ...
So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it moudlo 1000000007.
Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:
F(n) = 2*F(n-1) + 3*F(n-2) with F(1)=1 and F(2) =2
So the series becomes:
1 2 7 20 61 ...
So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it moudlo 1000000007.
Inputs
First line will contain "T" the no. of test cases. Each of the next "T" lines will contain an integer N, the term which Butters wants to find out.
Outputs :
For each test case print the Nth term of this series modulo 1000000007.
For each test case print the Nth term of this series modulo 1000000007.
Constraints
1 <= T <= 10^5 , 1 <= N <= 10^9
1 <= T <= 10^5 , 1 <= N <= 10^9
Level : Thinker,Admirer
Solution to the Problem :
//this is an O(log n) solution for finding the nth fibonacci number
#include<stdio.h>
long long int mod =1000000007;
void multiply(long long int m[][2],long long int n[][2])
{
long long int c00=((m[0][0]*n[0][0])%mod+(m[0][1]*n[1][0])%mod)%mod;
long long int c01=((m[0][0]*n[0][1])%mod+(m[0][1]*n[1][1])%mod)%mod;
long long int c02=((m[1][0]*n[0][0])%mod+(m[1][1]*n[1][0])%mod)%mod;
long long int c03=((m[1][0]*n[0][1])%mod+(m[1][1]*n[1][1])%mod)%mod;
m[0][0]=c00;
m[0][1]=c01;
m[1][0]=c02;
m[1][1]=c03;
}
void power(long long int m[][2],long long int n)
{
if(n==1)
return;
if(n==2)
{
multiply(m,m);
return;
}
long long int temp[2][2];
temp[0][0]=m[0][0]%mod;
temp[0][1]=m[0][1]%mod;
temp[1][0]=m[1][0]%mod;
temp[1][1]=m[1][1]%mod;
power(m,n/2);
multiply(m,m);
if(n%2!=0)
multiply(m,temp);
}
void fibonacci(long long int n)
{
long long int m[2][2];
m[0][0]=2;
m[0][1]=1;
m[1][0]=3;
m[1][1]=0;
power(m,n-2);
long long int x[2][2]={7,2,2,1};
multiply(x,m);
printf("%lld\n",x[1][0]%mod);
}
main()
{
long long int t;
scanf("%lld",&t);
while(t--)
{
long long int k;
scanf("%lld",&k);
if(k==1)
printf("1\n");
else if(k==2)
printf("2\n");
else
fibonacci(k);
}
}
}
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]);
}
}
