Submission #525839

#	Time	Username	Problem	Language	Result	Execution time	Memory
525839		vijay	Robot (JOI21_ho_t4)	Java	0 / 100	689 ms	33844 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];
        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));
        }

        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.add(new State(0, 0));
        boolean[] visited = new boolean[N];
        long ans = -1;
        while(!pq.isEmpty()){
            State curr = pq.poll();
            if(visited[curr.pos]){
                continue;
            }

            visited[curr.pos] = true;

            if(curr.pos == N - 1){
                ans = curr.dist;
            }

            // go to each one and see the count
            HashMap<Integer, Integer> co = new HashMap<>();
            for(Road r: adj[curr.pos]){
                if(!co.containsKey(r.color)){
                    co.put(r.color, r.cost);
                } else {
                    co.put(r.color, co.get(r.color) + r.cost);
                }
            }

            for(Road r: adj[curr.pos]){
                if(co.size() != M){
                  pq.add(new State(r.to, curr.dist + co.get(r.color) - r.cost));
                } else {
                  pq.add(new State(r.to, Math.min(curr.dist + r.cost, curr.dist + co.get(r.color) - r.cost)));
                }
            }
        }

        System.out.println(ans);
    }

    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()); }
	}


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

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

    public static class Road {
        int a, to, color, cost;
        public Road(int a, int to, int color, int cost){
            this.a = a;
            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