Submission #17518103

---

Source Code Expand

//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

Judge Result