Submission #489959

#	Time	Username	Problem	Language	Result	Execution time	Memory
489959		rainliofficial	Robot (JOI21_ho_t4)	Java	34 / 100	3084 ms	196840 KiB

Main

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

public class Main {
    static int n, m;
    static ArrayList<Edge>[] arr;
    static HashMap<Integer, Long>[] recolor;
    static HashMap<Integer, Long>[][] dist;
    static int[] edgeColor, edgeCost;
    static PriorityQueue<State> pq;
    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 ArrayList[n];
        recolor = new HashMap[n];
        dist = new HashMap[n][2];
        for (int i=0; i<n; i++){
            arr[i] = new ArrayList<>();
            recolor[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++){
            st = new StringTokenizer(file.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            arr[s].add(new Edge(e, c, p, i));
            arr[e].add(new Edge(s, c, p, i));
            if (!recolor[s].containsKey(c)){
                recolor[s].put(c, 0L);
            }
            if (!recolor[e].containsKey(c)){
                recolor[e].put(c, 0L);
            }
            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 (dist[curr.node][curr.recolor].get(curr.prevEdge) < curr.cost){
                continue;
            }
            if (curr.node == n-1){
                System.out.println(curr.cost);
                System.exit(0);
            }
            for (Edge e : arr[curr.node]){
                if (e.id == curr.prevEdge){
                    continue;
                }
                long nc = recolor[curr.node].get(e.c) - e.p;
                if (curr.prevEdge != -1 && curr.recolor == 1 && e.c == edgeColor[curr.prevEdge]){
                    nc -= edgeCost[curr.prevEdge];
                }
                add(e.to, e.id, 0, curr.cost + nc);
                add(e.to, e.id, 1, curr.cost + e.p);
            }
        }
        System.out.println(-1);
    }
    public static void add(int node, int prevEdge, int recolor, long cost){
        if (!dist[node][recolor].containsKey(prevEdge) || cost < dist[node][recolor].get(prevEdge)){
            dist[node][recolor].put(prevEdge, cost);
            pq.add(new State(node, prevEdge, recolor, 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, recolor;
        long cost;
        public State(int node, int prevEdge, int recolor, long cost){
            this.node = node;
            this.prevEdge = prevEdge;
            this.recolor = recolor;
            this.cost = cost;
        }
        public int compareTo(State o){
            return Long.compare(this.cost, o.cost);
        }
    }
}

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