[HackerEarth] Pizzahub has started Home Delivery scheme in one of his restaurants. As the scheme is new , the Manager appoints only one employee to deliver food to various locations. The delivery boy - P18687

题目描述

Pizzahub has started Home Delivery scheme in one of his restaurants. As the scheme is new , the Manager appoints only one employee to deliver food to various locations. The delivery boy who has been appointed is an absent-minded chap. He always forgets to fill fuel in his delivery scooter. So what he does is that whenever the Manager sends him for delivery, he goes to the gas station from the restaurant first. He gets his tank filled and then he heads towards his destination. He will do this every single time irrespective of the destination. The delivery boy tries his best to be on time. And to do this, he will choose those paths(from restaurant to gas station AND gas station to destinaion) which cost him the least amount of time. Your task is to tell the Manager how much time can the delivery boy save if he had enough fuel in his scooter i.e. if he went to the destination directly without stopping for fuel (taking the path which costs him least amount of time).
The city has N streets numbered from 0 to N-1. The restaurant is on street number S, the gas station is on street number G and the food has to be delivered to street D . Note that S, G and D need not be distinct.
Input:

First line of the input contains a single integer N.
Then follows an NxN matrix T which is represented in N lines with N space separated integers on each line.
T[i][j] denotes the time taken to move from the ith street to jth street. Obviously, T[i][i] = 0.
Next line contains a single integer M, the number of scenarios.
The following M lines contain 3 space separated integers S, G and D.
Output:

For each of the M scenarios, output the time taken by the delivery boy to deliver the food and the time he could have saved if he went directly from S to D.
Both these values must be on the same line separated by a single space.
Constraints:

1 ≤ N ≤ 100
1 ≤ M ≤ 10000
0 ≤ T[i][j] ≤ 100000
0 ≤ S,G,D ≤ N-1

SAMPLE INPUT
4
0 2 1 3
1 0 4 5
3 1 0 3
1 1 1 0
4
0 2 1
0 2 2
3 1 2
3 0 1

SAMPLE OUTPUT
2 0
1 0
3 2
3 2

输入格式

见题面

输出格式

见题面

样例输入

10
63399 78153 93132 39336 68154 774 97339 72087 16358 
0 92624 32544 85360 55288 1442 98884 14301 62548 
51168 0 25721 90772 5907 31108 46955 22347 74588 
417 48145 0 12745 80168 26299 5877 19504 10805 
33195 99245 39361 0 11224 8221 71905 96584 79862 
95468 94163 68599 90794 0 61684 94320 81566 67591 
44874 6290 16368 3538 6707 0 64514 32635 3227 
54864 22731 17970 77867 72278 17215 0 17228 83502 
5486 80086 21651 11537 91907 32166 80137 0 82701 
90809 80620 77793 32590 25494 84084 48958 45384 0 
144
2 1
6 4
6 3
6 5
2 4
0 1
9 4
8 6
8 2
9 7
3 1
3 7
5 3
4 0
1 4
0 6
8 5
5 6
7 4
5 5
6 9
9 4
8 9
2 3
1 6
5 9
3 7
4 2
4 1
6 6
7 3
9 4
0 4
7 8
4 9
8 6
8 0
3 6
7 0
5 8
8 5
1 6
9 9
7 6
0 3
9 1
0 9
8 4
0 1
4 6
7 7
2 0
6 9
3 8
1 0
8 2
1 2
9 2
1 2
5 7
0 4
1 8
0 4
0 0
6 3
6 1
8 4
0 3
0 6
1 2
1 4
8 7
7 9
6 9
7 6
6 4
0 2
7 4
5 4
7 8
6 9
9 0
2 9
2 5
2 4
7 1
3 3
6 0
0 5
2 4
9 0
0 1
0 6
8 8
6 3
3 2
5 6
9 2
7 4
4 8
9 9
4 1
2 2
8 0
2 8
2 4
3 9
7 8
1 7
3 2
2 3
1 7
3 0
2 0
9 4
9 6
3 9
6 6
0 0
1 5
2 7
2 0
6 4
4 6
5 7
4 8
9 1
3 7
7 0
8 1
4 3
3 7
1 6
2 0
3 7
0 1
4 2
8 7
2 6
6 7
5 1
6 6
8 9
5 1

样例输出

时间限制	2000 ms
内存限制	256 MB
难度	普及
提交数	0
通过数	0
通过率	0.0%

P18687 [HackerEarth] Pizzahub has started Home Delivery scheme in one of his restaurants. As the scheme is new , the Manager appoints only one employee to deliver food to various locations. The delivery boy

题目描述

输入格式

输出格式

样例输入

样例输出