Submission #490143

#	Time	Username	Problem	Language	Result	Execution time	Memory
490143		rainliofficial	Robot (JOI21_ho_t4)	Java	34 / 100	3099 ms	210284 KiB

Main

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

public class Main {
    static int n, m;
    static HashMap<Integer, ArrayList<Edge>>[] arr;
    static HashMap<Integer, Long>[] recolor;
    // static long[] dp; // dp[i] = min dist to get to node i
    // static HashMap<Integer, Long>[] dp2; // dp2[i][c] = min cost to get to i, given we just recolored an edge of color c
    static HashMap<Integer, Long>[][] dist;
    static int[] edgeColor, edgeCost;
    static PriorityQueue<State> pq;
    public static void main(String[] args) throws IOException{
        FastIO file = new FastIO();
        // BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader file = new BufferedReader(new FileReader("file.in"));
        // PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Robot.out")));
        n = file.nextInt();
        m = file.nextInt();
        arr = new HashMap[n];
        recolor = new HashMap[n];
        dist = new HashMap[n][2];
        // dp = new long[n];
        // dp2 = new HashMap[n];
        for (int i=0; i<n; i++){
            arr[i] = new HashMap<>();
            recolor[i] = new HashMap<>();
            // dp2[i] = new HashMap<>();
            dist[i][0] = new HashMap<>();
            dist[i][1] = new HashMap<>();
        }
        int[] edgeColor = new int[m];
        int[] edgeCost = new int[m];
        for (int i=0; i<m; i++){
            int s = file.nextInt()-1;
            int e = file.nextInt()-1;
            int c = file.nextInt();
            int p = file.nextInt();
            if (!recolor[s].containsKey(c)){
                recolor[s].put(c, 0L);
                arr[s].put(c, new ArrayList<>());
            }
            if (!recolor[e].containsKey(c)){
                recolor[e].put(c, 0L);
                arr[e].put(c, new ArrayList<>());
            }
            arr[s].get(c).add(new Edge(e, c, p, i));
            arr[e].get(c).add(new Edge(s, c, p, i));
            recolor[s].put(c, recolor[s].get(c) + p);
            recolor[e].put(c, recolor[e].get(c) + p);
            edgeColor[i] = c;
            edgeCost[i] = p;
        }
        pq = new PriorityQueue<>();
        add(0, -1, 0, 0);
        while (!pq.isEmpty()){
            State curr = pq.poll();
            if (curr.colorLater == 1){
                // We recolored the edge we walked through, so only loop through edges of the same color
                if (dist[curr.node][1].get(edgeColor[curr.prevEdge]) != curr.cost){
                    continue;
                }
                for (Edge e : arr[curr.node].get(edgeColor[curr.prevEdge])){
                    if (e.id == curr.prevEdge){
                        continue;
                    }
                    long nc = curr.cost + recolor[curr.node].get(e.c) - e.p;
                    if (!dist[e.to][0].containsKey(-1) || nc < dist[e.to][0].get(-1)){
                        pq.add(new State(e.to, e.id, 0, nc));
                        dist[e.to][0].put(-1, nc);
                    }
                }
            }else{
                if (dist[curr.node][0].get(-1) != curr.cost){
                    continue;
                }
                // We didn't recolor the previous edge, so loop through all colors
                for (int color : arr[curr.node].keySet()){
                    for (Edge e : arr[curr.node].get(color)){
                        if (e.id == curr.prevEdge){
                            continue;
                        }
                        // Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
                        long case1 = curr.cost + e.p;
                        if (!dist[e.to][0].containsKey(-1) || case1 < dist[e.to][0].get(-1)){
                            dist[e.to][0].put(-1, case1);
                            pq.add(new State(e.to, e.id, 0,case1));
                        }   
                        // Recolor all other edges
                        long case2 = curr.cost + recolor[curr.node].get(e.c) - e.p;
                        if (!dist[e.to][0].containsKey(-1) || case2 < dist[e.to][0].get(-1)){
                            dist[e.to][0].put(-1, case2);
                            pq.add(new State(e.to, e.id, 0, case2));
                        }
                        // Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
                        // to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
                        long case3 = curr.cost;
                        if (!dist[e.to][1].containsKey(e.c) || case3 < dist[e.to][1].get(e.c)){
                            dist[e.to][1].put(e.c, case3);
                            pq.add(new State(e.to, e.id, 1, case3));
                        }
                    }
                }
            }
        }
        long ans = Long.MAX_VALUE;
        for (long d : dist[n-1][0].values()){
            ans = Math.min(ans, d);
        }
        if (ans == Long.MAX_VALUE) ans = -1;
        file.println(ans);
        file.close();
    }
    public static void add(int node, int prevEdge, int colorLater, long cost){
        if (!dist[node][colorLater].containsKey(prevEdge) || cost < dist[node][colorLater].get(prevEdge)){
            dist[node][colorLater].put(prevEdge, cost);
            pq.add(new State(node, prevEdge, colorLater, cost));
        }
    }
    static class Edge{
        int to, c, p, id;
        public Edge(int to, int c, int p, int id){
            this.to = to;
            this.c = c;
            this.p = p;
            this.id = id;
        }
    }
    static class State implements Comparable<State>{
        int node, prevEdge, colorLater;
        long cost;
        public State(int node, int prevEdge, int colorLater, long cost){
            this.node = node;
            this.prevEdge = prevEdge;
            this.colorLater = colorLater;
            this.cost = cost;
        }
        public int compareTo(State o){
            return Long.compare(this.cost, o.cost);
        }
    }

    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1<<16];
        private int curChar, numChars;
    
        // standard input
        public FastIO() { this(System.in,System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            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() { // nextLong() would be implemented similarly
            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 double nextDouble() { return Double.parseDouble(next()); }
    }
}

Compilation message (stderr)

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

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42