Submission #489731

#	Time	Username	Problem	Language	Result	Execution time	Memory
489731		rainliofficial	Robot (JOI21_ho_t4)	Java	0 / 100	3076 ms	155460 KiB

Main

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

public class Main {
    static int n, m;
    static ArrayList<Edge>[] arr;
    static HashMap<Integer, Integer>[] dist;
    //static HashMap<Integer, ArrayList<Edge>>[] arr;
    static HashMap<Integer, Integer>[] recolor; // Stores the cost to recolor all edges of a certain color at a node

    public static void main(String[] args) throws IOException{
        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")));
        StringTokenizer st = new StringTokenizer(file.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        //arr = new HashMap[n];
        arr = new ArrayList[n];
        recolor = new HashMap[n];
        dist = new HashMap[n];
        recolor  = new HashMap[n];
        for (int i=0; i<n; i++){
            arr[i] = new ArrayList<>();
            recolor[i] = new HashMap<>();
            dist[i] = new HashMap<>();
            recolor[i] = new HashMap<>();
        }
        for (int i=0; i<m; i++){
            st = new StringTokenizer(file.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            int color = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            arr[s].add(new Edge(e, color, cost));
            arr[e].add(new Edge(s, color, cost));
            addEdge(s, e, color, cost);
            addEdge(e, s, color, cost);
        }
        // Do Dijkstra on expanded states. State = current node, the original color of the edge we just walked through,
        // (if we recolored it). Total N+M states. 
        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.add(new State(0, -1, 0, 0));
        while (!pq.isEmpty()){
            State curr = pq.poll();
            if (dist[curr.node].containsKey(curr.prevColor) && dist[curr.node].get(curr.prevColor) != curr.cost){
                continue; 
            }
            addUsed(curr.node, curr.prevColor, curr.cost);
            for (Edge e : arr[curr.node]){
                // if (curr.prevColor == e.color || curr.prevColor == -1){
                    if (!recolor[curr.node].containsKey(e.color)){
                        continue;
                    }
                    // Determine to recolor all other edges of the same color, or recolor this 1 edge
                    // if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost <= e.cost){
                        // Recolor everything else
                        int nc = curr.cost + recolor[curr.node].get(e.color) - e.cost;
                        if (curr.prevColor == e.color){
                            nc -= curr.prevEdgeCost;
                        }
                        if (addUsed(e.to, -1, nc)){
                            pq.add(new State(e.to, -1, nc, e.cost));
                        }
                    // }else if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost >= e.cost){
                        if (addUsed(e.to, e.color, curr.cost + e.cost)){
                            pq.add(new State(e.to, e.color, curr.cost + e.cost, e.cost));
                        }
                    // }
                // }
            }
            // if (curr.prevColor != -1){
            //     // Loop through the edges with color = prevColor
            //     for (Edge e : arr[curr.node].get(curr.prevColor)){
            //         if (recolor[curr.node].get(curr.prevColor) - curr.prevEdgeCost >;
            //         if (dist[e.to].containsKey(e.color) && dist[e.to].get(e.color) <= nc + curr.cost){

            //         }
            //     }
            // }else{
            //     for (int color : arr[curr.node].keySet()){
            //         for (Edge e : arr[curr.node].get(color)){

            //         }
            //     }
            // }

        }
        int ans = Integer.MAX_VALUE;
        for (int c : dist[n-1].keySet()){
            ans = Math.min(dist[n-1].get(c), ans);
        }
        if (ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }
    public static void addEdge(int ind, int to, int color, int cost){
        if (!recolor[ind].containsKey(color)){
            // arr[ind].put(color, new ArrayList<>());
            recolor[ind].put(color, 0);
        }
        // arr[ind].get(color).add(new Edge(to, color, cost));
        recolor[ind].put(color, recolor[ind].get(color) + cost);
    }
    public static boolean addUsed(int ind, int prevColor, int newDist){ // Return true if element added, or false if not added
        if (!dist[ind].containsKey(prevColor) || dist[ind].get(prevColor) > newDist){
            dist[ind].put(prevColor, newDist);
            return true;
        }
        return false;
    }
    static class State implements Comparable<State>{
        int node, prevColor, cost, prevEdgeCost;
        public State(int node, int prevColor, int cost, int prevEdgeCost){
            this.node = node;
            this.prevColor = prevColor;
            this.cost = cost;
            this.prevEdgeCost = prevEdgeCost;
        }
        public int compareTo(State o){
            return Integer.compare(this.cost, o.cost);
        }
    }
    static class Edge{
        int to, color, cost;
        public Edge(int to, int color, int cost){
            this.to = to;
            this.color = color;
            this.cost = cost;
        }
    }
}

Compilation message (stderr)

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

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