제출 #513804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513804		rainliofficial	Cities (BOI16_cities)	Java	0 / 100	678 ms	58296 KiB

cities

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

public class cities {
    static int n, k, m, INF = (int)1e9;
    static ArrayList<Edge>[] arr;
    static int[] target;
    static int[][] dp;
    public static void main(String[] args) throws IOException{
        FastIO file = new FastIO();
        n = file.nextInt();
        k = file.nextInt();
        m = file.nextInt();
        arr = new ArrayList[n];
        for (int i=0; i<n; i++) {
            arr[i] = new ArrayList<>();
        }
        target = new int[n];
        for (int i=0; i<k; i++) {
            target[i] = file.nextInt()-1;
        }
        for (int i=0; i<m; i++) {
            int a = file.nextInt()-1;
            int b = file.nextInt()-1;
            int c = file.nextInt();
            arr[a].add(new Edge(b, c));
            arr[b].add(new Edge(a, c));
        }
        dp = new int[n][1<<k];
        for (int i=0; i<n; i++){
            Arrays.fill(dp[i], INF);
            dp[i][0] = 0;
        }
        for (int i=0; i<k; i++){
            dp[target[i]][1<<i] = 0;
        }
        for (int i=1; i<(1<<k); i++){
            for (int j=0; j<i; j++){
                if ((i | j) != i){
                    continue;
                }
                // if ((i^j) > j){
                //     continue;
                // }
                for (int v=0; v<n; v++){
                    dp[v][i] = Math.min(dp[v][i], dp[v][j] + dp[v][i^j]);
                }
            }
            PriorityQueue<State> pq = new PriorityQueue<>();
            for (int j=0; j<n; j++){
                if (dp[j][i] != INF){
                    pq.add(new State(j, dp[j][i]));
                }
            }
            boolean[] used = new boolean[n];
            while (!pq.isEmpty()){
                State curr = pq.poll();
                if (used[curr.at]){
                    continue;
                }
                used[curr.at] = true;
                for (Edge j : arr[curr.at]){
                    if (dp[j.to][i] > curr.cost + j.cost){
                        dp[j.to][i] = curr.cost + j.cost;
                        pq.add(new State(j.to, dp[j.to][i]));
                    }
                }
            }
        }
        int full = (1<<k) - 1;
        int ans = INF;
        for (int i=0; i<n; i++){
            ans = Math.min(ans, dp[i][full]);
        }
        file.println(ans);
        file.close();
    }
    static class State implements Comparable<State>{
        int at, cost;
        public State(int at, int cost){
            this.at = at;
            this.cost = cost;
        }
        public int compareTo(State o){
            return this.cost - o.cost;
        }
    }
    static class Edge{
        int to, cost;
        public Edge(int to, int cost){
            this.to = to;
            this.cost = cost;
        }

    }
    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1<<16];
        private int curChar, numChars;
    
        public FastIO() { this(System.in,System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }
        public FastIO(String i) throws IOException {
            super(System.out);
            stream = new FileInputStream(i);
        }
        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }
        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c; do { c = nextByte(); } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
            return res.toString();
        }
        public int nextInt() {
            int c; do { c = nextByte(); } while (c <= ' ');
            int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10*res+c-'0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
        public long nextLong() {
            int c; do { c = nextByte(); } while (c <= ' ');
            int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10*res+c-'0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
        public double nextDouble() { return Double.parseDouble(next()); }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: cities.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26