oj.uz

답안 #1036263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036263 2024-07-27T07:33:40 Z Oz121 Robot (JOI21_ho_t4) Java 11
34 / 100
 3000 ms 159160 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); 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;
        }

        @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
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 9624 KB Output is correct
2 Correct 53 ms 9936 KB Output is correct
3 Correct 58 ms 9732 KB Output is correct
4 Correct 55 ms 9944 KB Output is correct
5 Correct 71 ms 9664 KB Output is correct
6 Correct 62 ms 9704 KB Output is correct
7 Correct 224 ms 20752 KB Output is correct
8 Correct 175 ms 18936 KB Output is correct
9 Correct 550 ms 20080 KB Output is correct
10 Correct 498 ms 22616 KB Output is correct
11 Correct 646 ms 19456 KB Output is correct
12 Correct 507 ms 24068 KB Output is correct
13 Correct 714 ms 23624 KB Output is correct
14 Correct 718 ms 23000 KB Output is correct
15 Correct 169 ms 14924 KB Output is correct
16 Correct 280 ms 19172 KB Output is correct
17 Correct 253 ms 20112 KB Output is correct
18 Correct 97 ms 11872 KB Output is correct
19 Correct 355 ms 21616 KB Output is correct
20 Correct 225 ms 14836 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1468 ms 102348 KB Output is correct
2 Correct 742 ms 60344 KB Output is correct
3 Execution timed out 3068 ms 159160 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 9624 KB Output is correct
2 Correct 53 ms 9936 KB Output is correct
3 Correct 58 ms 9732 KB Output is correct
4 Correct 55 ms 9944 KB Output is correct
5 Correct 71 ms 9664 KB Output is correct
6 Correct 62 ms 9704 KB Output is correct
7 Correct 224 ms 20752 KB Output is correct
8 Correct 175 ms 18936 KB Output is correct
9 Correct 550 ms 20080 KB Output is correct
10 Correct 498 ms 22616 KB Output is correct
11 Correct 646 ms 19456 KB Output is correct
12 Correct 507 ms 24068 KB Output is correct
13 Correct 714 ms 23624 KB Output is correct
14 Correct 718 ms 23000 KB Output is correct
15 Correct 169 ms 14924 KB Output is correct
16 Correct 280 ms 19172 KB Output is correct
17 Correct 253 ms 20112 KB Output is correct
18 Correct 97 ms 11872 KB Output is correct
19 Correct 355 ms 21616 KB Output is correct
20 Correct 225 ms 14836 KB Output is correct
21 Correct 1468 ms 102348 KB Output is correct
22 Correct 742 ms 60344 KB Output is correct
23 Execution timed out 3068 ms 159160 KB Time limit exceeded
24 Halted 0 ms 0 KB -