Monday, 17 August 2015

USA Tour

Standard
In the state of USA Mr. Adam is a renowned architect. The way in which he has connected the cities is quite interesting.

There are N cities in USA and between any two cities there is a direct one way road connecting them.
Mr Adam has planned a tour so that he can visit all the cities in the state and greet his people. He asks for your help.

The task is to visit all the cities using existing road network but Mr Adam does not want to visit any city more than once on his tour. There may be many possible routes to do this task so suggest him the one which has smallest possible distance.

Input Format:
The first line of input contains an integer N, the number of cities.
Then follow, N lines each containing N integers. These NxN numbers represent the connectivity matrix of cities. The number at position (i, j) indicates the length of direct road from city i to city j. Cities are numbered 0 to N-1.

Output Format:
Print a list of N, space separated integers which denote the order in which the cities should be visited.

Constraints:
N <= 1000

Scoring:
The score for a correct sequence of cities depends on the total path length of the tour.
Score = [[10(N-1)-tourLength]/10(N-1)]*20.

Explanation for Sample Input/Output:
The path 2->1->0 is of length 10+5 =15. So the score is calculated as:
A = 10*2-15 = 5;
B = (5/20)*20 = 5;
Score = 5.00;

Sample Input
3
0 0 0
5 0 0
6 10 0
Sample Output
2 1 0

Time Limit: 10 sec(s) for all input files combined.
Memory Limit: 256 MB
Source Limit: 1024 KB 
 
Code:
 
/* IMPORTANT: class must not be public. */

/*
 * uncomment this if you want to read input.
import java.io.BufferedReader;
import java.io.InputStreamReader;
*/
import java.util.Scanner;

class TestClass
{
    public static void main(String args[] ) throws Exception
    {
        Scanner scanner = new Scanner(System.in);
        int noOfCitys = 1;
        noOfCitys = Integer.parseInt(scanner.next());
       
        int[][] matrix = new int[noOfCitys][noOfCitys];
       
        for (int i=0; i<noOfCitys; i++)
        {
            for (int j=0; j<noOfCitys; j++)
            {
                matrix[i][j] = Integer.parseInt(scanner.next());
                System.out.println(    matrix[i][j]);
            }
        }
       
       
       
       
//        System.out.println(noOfCitys);
    }

0 comments:

Post a Comment