Submission #526141

#	Time	Username	Problem	Language	Result	Execution time	Memory
526141		vijay	Robot (JOI21_ho_t4)	Java	0 / 100	3085 ms	568360 KiB

Main

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

public class Main {
    public static void main(String[] args) throws IOException, FileNotFoundException {
        // Scanner in = new Scanner(new File("test.in"));
        Kattio in = new Kattio();

        int N = in.nextInt();
        int M = in.nextInt();

        ArrayList<Road>[] adj = new ArrayList[N];
        HashMap<Integer, Long>[] costSum = new HashMap[N];
        HashMap<Integer, Long>[] dp2 = new HashMap[N];

        for(int i = 0; i < N; i++){
          costSum[i] = new HashMap<>();
          dp2[i] = new HashMap<>();
        }

        for(int i = 0; i < N; i++){
            adj[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int color = in.nextInt();
            int cost = in.nextInt();
            adj[a].add(new Road(a, b, color, cost));
            adj[b].add(new Road(b, a, color, cost));

            costSum[a].put(color, costSum[a].getOrDefault(color, 0l) + cost);
            costSum[b].put(color, costSum[a].getOrDefault(color, 0l) + cost);
        }

        long[] dp = new long[N];
        Arrays.fill(dp, Integer.MAX_VALUE);
        PriorityQueue<State> pq = new PriorityQueue<>();
        dp[0] = 0;
        pq.add(new State(0, 0, 0));

        while(!pq.isEmpty()){
          State curr = pq.poll();

          if(curr.fromColor != 0){
            if(dp2[curr.pos].get(curr.fromColor) != curr.dist){
              continue;
            }

            for(Road r: adj[curr.pos]){
              if(r.color == curr.fromColor){
                long cost = costSum[r.from].get(curr.fromColor) - r.cost;
                if(cost + curr.dist < dp[r.to]){
                  dp[r.to] = curr.dist + cost;
                  pq.add(new State(r.to, 0, dp[r.to]));
                }
              }
            }
          } else {
            if(dp[curr.pos] != curr.dist){
              continue;
            }

            for(Road r: adj[curr.pos]){
              // don't flip this one
              long cost = costSum[r.from].get(r.color) - r.cost + curr.dist;
              if(cost < dp[r.to]){
                dp[r.to] = cost;
                pq.add(new State(r.to, 0, dp[r.to]));
              }

              // flip this one
              cost = curr.dist + r.cost;
              if(cost < dp[r.to]){
                dp[r.to] = cost;
                pq.add(new State(r.to, 0, dp[r.to]));
              }

              // flip j and another edge of the same color
              cost = curr.dist;
              if(!dp2[r.to].containsKey(r.color) || cost < dp2[r.to].get(r.color)){
                dp2[r.to].put(r.color, cost);
                pq.add(new State(r.to, r.color, cost));
              }
            }
          }
        }

        System.out.println(dp[N - 1] == Integer.MAX_VALUE ? -1 : dp[N - 1]);
    }

    public static class State implements Comparable<State>{
        int pos;
        int fromColor;
        long dist;
        public State(int pos, int fromColor, long dist){
            this.pos = pos;
            this.fromColor = fromColor;
            this.dist = dist;
        }

        public int compareTo(State s){
            return Long.compare(dist, s.dist);
        }
    }

    public static class Road {
        int from, to, color, cost;
        public Road(int a, int to, int color, int cost){
            this.from = a;
            this.to = to;
            this.color = color;
            this.cost = cost;
        }
    }

    static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;

		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(new FileWriter(problemName + ".out"));
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}

		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}

		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
}

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