oj.uz

Submission #1036264

# Submission time Handle Problem Language Result Execution time Memory
1036264 2024-07-27T07:36:42 Z Oz121 Robot (JOI21_ho_t4) Java 11
34 / 100
 3000 ms 167896 KB 
import java.io.*;
import java.util.*;
public class Main {
    public static int num; public static int m;
    public static HashMap<Integer, Long>[] costs;
    public static void main(String[] args) throws IOException {
        FastIO io = new FastIO();
        num = io.nextInt(); m = io.nextInt();

        ArrayList<ArrayList<Edge>> adj = new ArrayList<>(); costs = new HashMap[num];
        for (int i = 0;i<num;i++) {
            adj.add(new ArrayList<>()); costs[i] = new HashMap<>();
        }

        for (int i = 0;i<m;i++) {
            int a = io.nextInt()-1; int b = io.nextInt()-1; int c = io.nextInt(); int d = io.nextInt();
            adj.get(a).add(new Edge(b,c,d)); adj.get(b).add(new Edge(a,c,d));

            costs[a].put(c, costs[a].getOrDefault(c,0L)+d); costs[b].put(c, costs[b].getOrDefault(c,0L)+d);
        }

        long ans = dijkstra(adj);
        if (ans==Long.MAX_VALUE) io.println(-1);
        else io.println(ans);
        io.close();
    }

    public static long dijkstra (ArrayList<ArrayList<Edge>> adj) {
        HashMap<Integer, Long>[][] dis = new HashMap[num][2];
        for (int i = 0;i<num;i++) {dis[i][0] = new HashMap<>(); dis[i][1] = new HashMap<>();}
        dis[0][0].put(-1,0L); dis[0][1].put(-1,0L);

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(i -> i.cost));
        pq.add(new Node(0,new Edge(-1,0,0),0,false));

        while (!pq.isEmpty()) {
            //System.out.println(pq);
            Node curr = pq.poll(); int node = curr.n; long d = curr.cost; Edge prev = curr.prev; boolean change = curr.change;
            if (dis[node][toI(change)].get(prev.n)!=d) continue;

            for (Edge e : adj.get(node)) {
                int n = e.n; int c = e.c; long w = e.w;
                if (n==prev.n) continue;

                long newD1 = d; long newD0 = d; //1 -> New change true; 0 -> New change false.
                if (change&&prev.c==c) {
                    newD1 += w; newD0 += costs[node].get(c)-prev.w-w;
                } else {
                    newD1 += w; newD0 += costs[node].get(c)-w;
                }

                if (newD0<dis[n][0].getOrDefault(node, Long.MAX_VALUE)) {
                    dis[n][0].put(node, newD0);
                    pq.add(new Node(n,new Edge(node,c,w),newD0,false));
                }

                if (newD1<dis[n][1].getOrDefault(node, Long.MAX_VALUE)) {
                    dis[n][1].put(node,newD1);
                    pq.add(new Node(n,new Edge(node,c,w),newD1,true));
                }
            }
        }

        long ans = Long.MAX_VALUE;
        for (Edge e : adj.get(num-1)) ans = Math.min(ans, Math.min(dis[num-1][0].getOrDefault(e.n, Long.MAX_VALUE),dis[num-1][1].getOrDefault(e.n, Long.MAX_VALUE)));
        return ans;
    }

    public static class Edge {
        int n; int c; long w;

        Edge (int n, int c, long w) {
            this.n = n; this.c = c; this.w = w;
        }
    }
    public static class Node {
        int n; Edge prev; long cost; boolean change;

        Node (int n, Edge prev, long cost, boolean change) {
            this.n = n; this.prev = prev; this.cost = cost; this.change = change;
        }
    }
    public static int toI (boolean b) {
        return b ? 1 : 0;
    }

    public static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;
        public FastIO() { this(System.in, System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        private int nextByte() {
            if (numChars == -1) { throw new InputMismatchException(); }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) { throw new InputMismatchException(); }
                if (numChars == -1) {
                    return -1;  // end of file
                }
            }
            return buf[curChar++];
        }
        public int nextInt() {
            int c;
            do { c = nextByte(); } while (c <= ' ');
            int sgn = 1;
            if (c == '-') { sgn = -1; c = nextByte(); }
            int res = 0;
            do {
                if (c < '0' || c > '9') { throw new InputMismatchException(); }
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
    }
}

Compilation message

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

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9652 KB Output is correct
2 Correct 52 ms 9664 KB Output is correct
3 Correct 58 ms 9584 KB Output is correct
4 Correct 54 ms 9668 KB Output is correct
5 Correct 67 ms 10156 KB Output is correct
6 Correct 60 ms 9964 KB Output is correct
7 Correct 174 ms 20152 KB Output is correct
8 Correct 161 ms 19320 KB Output is correct
9 Correct 454 ms 19620 KB Output is correct
10 Correct 416 ms 23052 KB Output is correct
11 Correct 520 ms 19620 KB Output is correct
12 Correct 395 ms 23384 KB Output is correct
13 Correct 603 ms 21636 KB Output is correct
14 Correct 595 ms 21400 KB Output is correct
15 Correct 98 ms 12328 KB Output is correct
16 Correct 189 ms 18204 KB Output is correct
17 Correct 180 ms 19628 KB Output is correct
18 Correct 63 ms 10548 KB Output is correct
19 Correct 272 ms 21372 KB Output is correct
20 Correct 154 ms 13672 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 109636 KB Output is correct
2 Correct 614 ms 60688 KB Output is correct
3 Execution timed out 3045 ms 167896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9652 KB Output is correct
2 Correct 52 ms 9664 KB Output is correct
3 Correct 58 ms 9584 KB Output is correct
4 Correct 54 ms 9668 KB Output is correct
5 Correct 67 ms 10156 KB Output is correct
6 Correct 60 ms 9964 KB Output is correct
7 Correct 174 ms 20152 KB Output is correct
8 Correct 161 ms 19320 KB Output is correct
9 Correct 454 ms 19620 KB Output is correct
10 Correct 416 ms 23052 KB Output is correct
11 Correct 520 ms 19620 KB Output is correct
12 Correct 395 ms 23384 KB Output is correct
13 Correct 603 ms 21636 KB Output is correct
14 Correct 595 ms 21400 KB Output is correct
15 Correct 98 ms 12328 KB Output is correct
16 Correct 189 ms 18204 KB Output is correct
17 Correct 180 ms 19628 KB Output is correct
18 Correct 63 ms 10548 KB Output is correct
19 Correct 272 ms 21372 KB Output is correct
20 Correct 154 ms 13672 KB Output is correct
21 Correct 1332 ms 109636 KB Output is correct
22 Correct 614 ms 60688 KB Output is correct
23 Execution timed out 3045 ms 167896 KB Time limit exceeded
24 Halted 0 ms 0 KB -