Minimun Shopping Cost (Samu and Shopping Problem)

Samu is in super market and in a mood to do a lot of shopping. She needs to buy shirts, pants and shoes for herself and her family. There are N different shops. Each shop contains all these three items but at different prices. Now Samu has a strategy that she won't buy the same item from the current shop if she had already bought that item from the shop adjacent to the current shop.

Now Samu is confused, because although she want to follow her strategy strictly but at the same time she want to minimize the total money she spends on shopping. Being a good programmer, she asks for your help.

You are provided description about all N shops i.e costs of all three items in each shop. You need to help Samu find minimum money that she needs to spend such that she buys exactly one item from every shop.

Input Format:
First line contain number of test cases T. Each test case in its first line contain N denoting the number of shops in Super Market. Then each of next N lines contains three space separated integers denoting cost of shirts, pants and shoes in that particular shop.

Output Format:
For each test case, output the minimum cost of shopping taking the mentioned conditions into account in a separate line.

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 105
Cost of each item (shirt/pant/shoe) does not exceed 104

Sample Input
1
3
1 50 50
50 50 50
1 50 50

Sample Output
52

Explanation
There are two ways, each one gives 52 as minimum cost. One way is buy shirt from first shop, pant from second shop and shirt from third shop or she can buy shirt from first shop, shoe from second shop and shirt from third shop.

Both ways , cost comes up to 1 + 50 + 1 = 52

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

import java.util.*; import java.io.*; public class HelloWorld{ public static void main(String []args){ Scanner scan = new Scanner(System.in); String line = System.getProperty("line.separator"); scan.useDelimiter(line); int cases = scan.nextInt(); int []value = new int[cases]; for(int x=0;x<cases;x++){ int N = scan.nextInt(); String []data = new String[N]; for(int y=0;y<N;y++){ data[y] = scan.next(); } int temp=0; for(int z=0;z<N;z++){ String []get = data[z].split(" "); int min = Integer.parseInt(get[0]); for(int a=0;a<get.length;a++){ if(Integer.parseInt(get[a])<min) min = Integer.parseInt(get[a]); } temp = temp+min; } value[x]= temp; } for(int b=0;b<value.length;b++) System.out.println(value[b]); } }