Submission #520233

#	Time	Username	Problem	Language	Result	Execution time	Memory
520233		Ste	Robot (JOI21_ho_t4)	Java	0 / 100	3114 ms	720212 KiB

Main

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer line = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(line.nextToken());
        int m = Integer.parseInt(line.nextToken());
        ArrayList<Edge>[] graph = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<Edge>();
        }
        for(int i = 0; i < m; i++) {
            line = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(line.nextToken()) - 1;
            int b = Integer.parseInt(line.nextToken()) - 1;
            int c = Integer.parseInt(line.nextToken()) - 1;
            int p = Integer.parseInt(line.nextToken());
            graph[a].add(new Edge(b, c, p));
            graph[b].add(new Edge(a, c, p));
        }
        int[] colors = new int[m];
        for(int i = 0; i < n; i++) {
            for(Edge e : graph[i]) {
                colors[e.c] += e.p;
            }
            for(Edge e : graph[i]) {
                e.w = colors[e.c] - e.p;
            }
            for(Edge e : graph[i]) {
                colors[e.c] = 0;
            }
        }
        PriorityQueue<Step> pq = new PriorityQueue<Step>();
        pq.add(new Step(0, -1, 0));
        long[] dp1 = new long[n];
        Arrays.fill(dp1, Long.MAX_VALUE);
        HashMap<Integer, Long>[] dp2 = new HashMap[n];
        for(int i = 0; i < n; i++) {
            dp2[i] = new HashMap<Integer, Long>();
        }
        while(pq.size() > 0) {
            Step cur = pq.poll();
            if(cur.c == -1) {
                if(cur.d >= dp1[cur.n]) {
                    continue;
                }
                dp1[cur.n] = cur.d;
                if(cur.n == n - 1) {
                    break;
                }
                for(Edge e : graph[cur.n]) {
                    pq.add(new Step(e.to, -1, cur.d + Math.min(e.p, e.w)));
                    pq.add(new Step(e.to, e.c, cur.d));
                }
            }else {
                Long min = dp2[cur.n].get(cur.c);
                if(min != null && cur.d >= min) {
                    continue;
                }
                dp2[cur.n].put(cur.c, cur.d);
                for(Edge e : graph[cur.n]) {
                    if(e.c == cur.c) {
                        pq.add(new Step(e.to, -1, cur.d + e.w));
                        pq.add(new Step(e.to, e.c, cur.d + e.w));
                    }
                }
            }
        }
        if(dp1[n - 1] == Long.MAX_VALUE) {
            out.println(-1);
        }else {
            out.println(dp1[n - 1]);
        }
        in.close();
        out.close();
    }
    static class Step implements Comparable<Step> {
        int n, c;
        long d;
        Step(int nn, int cc, long dd) {
            n = nn;
            c = cc;
            d = dd;
        }
        @Override
        public int compareTo(Step o) {
            if(d > o.d) {
                return 1;
            }else if(d < o.d) {
                return -1;
            }else {
                return 0;
            }
        }
    }
    static class Edge {
        int to, c, p, w;
        Edge(int t, int cc, int pp) {
            to = t;
            c = cc;
            p = pp;
        }
    }
}

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