Submission #17518103


Source Code Expand

Copy
//package atcoder.beginner180;

import java.io.*;
import java.util.*;

public class Main {
    static InputReader in;
    static PrintWriter out;

    public static void main(String[] args) {
        //initReaderPrinter(true);
        initReaderPrinter(false);
        //solve(in.nextInt());
        solve(1);
    }

    static void solve(int testCnt) {
        for (int testNumber = 0; testNumber < testCnt; testNumber++) {
            int n = in.nextInt();
            int[][] p = new int[n][3];
            for(int i = 0; i < n; i++) {
                p[i][0] = in.nextInt();
                p[i][1] = in.nextInt();
                p[i][2] = in.nextInt();
            }

            int[][] dp = new int[1 << n][n];
            for(int[] e : dp) {
                Arrays.fill(e, Integer.MAX_VALUE);
            }

            dp[1][0] = 0;
            for(int i = 1; i < dp.length; i++) {
                if((i & 1) == 0) {
                    continue;
                }
                //given dp[i][j], compute the next move, j is the next city to visit
                for(int j = 0; j < n; j++) {
                    int next = i | (1 << j);
                    for(int k = 0; k < n; k++) {
                        if((i & (1 << k)) == 0) {
                            continue;
                        }
                        dp[next][j] = Math.min(dp[next][j], dp[i][k] + Math.abs(p[j][0] - p[k][0]) + Math.abs(p[j][1] - p[k][1]) + Math.max(0, p[j][2] - p[k][2]));
                    }

                }
            }
            out.println(dp[dp.length - 1][0]);
        }
        out.close();
    }

    static void initReaderPrinter(boolean test) {
        if (test) {
            try {
                in = new InputReader(new FileInputStream("src/input.in"));
                out = new PrintWriter(new FileOutputStream("src/output.out"));
            } catch (IOException e) {
                e.printStackTrace();
            }
        } else {
            in = new InputReader(System.in);
            out = new PrintWriter(System.out);
        }
    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        InputReader(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream), 32768);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        Integer[] nextIntArray(int n) {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        Long[] nextLongArray(int n) {
            Long[] a = new Long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }
    }
}


Submission Info

Submission Time
Task E - Traveling Salesman among Aerial Cities
User alexlin
Language Java (OpenJDK 1.8.0)
Score 500
Code Size 3749 Byte
Status AC
Exec Time 195 ms
Memory 38336 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 195 ms 38336 KB
random_02.txt AC 64 ms 25412 KB
random_03.txt AC 184 ms 38180 KB
random_04.txt AC 184 ms 38124 KB
random_05.txt AC 192 ms 38196 KB
random_06.txt AC 66 ms 25240 KB
random_07.txt AC 185 ms 38128 KB
random_08.txt AC 88 ms 27516 KB
random_09.txt AC 185 ms 38288 KB
random_10.txt AC 67 ms 25124 KB
random_11.txt AC 186 ms 38188 KB
random_12.txt AC 72 ms 25548 KB
random_13.txt AC 185 ms 38272 KB
random_14.txt AC 67 ms 25340 KB
random_15.txt AC 182 ms 38148 KB
random_16.txt AC 85 ms 26852 KB
random_17.txt AC 185 ms 38164 KB
random_18.txt AC 83 ms 26908 KB
random_19.txt AC 186 ms 38288 KB
random_20.txt AC 88 ms 27560 KB
sample_01.txt AC 67 ms 25336 KB
sample_02.txt AC 64 ms 25492 KB
sample_03.txt AC 187 ms 38200 KB