oj.uz

Submission #1036255

# Submission time Handle Problem Language Result Execution time Memory
1036255 2024-07-27T07:10:34 Z Oz121 Robot (JOI21_ho_t4) Java 11
0 / 100
 3000 ms 165048 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 {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        num = Integer.parseInt(l1.nextToken()); m = Integer.parseInt(l1.nextToken());

        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++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1; int c = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken());
            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) System.out.println(-1);
        else System.out.println(ans);
    }

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

        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 newD = d; boolean newChange;
                if (change&&prev.c==c) {
                    if (costs[node].get(c)-prev.w-w>w) {
                        newD += w; newChange = true;
                    } else {
                        newD += costs[node].get(c)-prev.w-w; newChange = false;
                    }
                } else {
                    if (costs[node].get(c)-w>w) {
                        newD += w; newChange = true;
                    } else {
                        newD += costs[node].get(c)-w; newChange = false;
                    }
                }

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

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

        @Override
        public String toString() {
            return n+" "+c+" "+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;
        }

        @Override
        public String toString() {
            return n+" ["+prev+"] "+cost+" "+change;
        }
    }

    public static int toI (boolean b) {
        return b ? 1 : 0;
    }
}

Compilation message

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

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9592 KB Output is correct
2 Correct 53 ms 9656 KB Output is correct
3 Correct 56 ms 9816 KB Output is correct
4 Correct 53 ms 9516 KB Output is correct
5 Correct 62 ms 10012 KB Output is correct
6 Correct 58 ms 9656 KB Output is correct
7 Correct 204 ms 17304 KB Output is correct
8 Correct 156 ms 17544 KB Output is correct
9 Incorrect 336 ms 19480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 81904 KB Output is correct
2 Correct 603 ms 46080 KB Output is correct
3 Correct 1628 ms 96188 KB Output is correct
4 Correct 736 ms 62272 KB Output is correct
5 Execution timed out 3040 ms 165048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9592 KB Output is correct
2 Correct 53 ms 9656 KB Output is correct
3 Correct 56 ms 9816 KB Output is correct
4 Correct 53 ms 9516 KB Output is correct
5 Correct 62 ms 10012 KB Output is correct
6 Correct 58 ms 9656 KB Output is correct
7 Correct 204 ms 17304 KB Output is correct
8 Correct 156 ms 17544 KB Output is correct
9 Incorrect 336 ms 19480 KB Output isn't correct
10 Halted 0 ms 0 KB -