oj.uz

Submission #470398

# Submission time Handle Problem Language Result Execution time Memory
470398 2021-09-03T16:24:17 Z rainliofficial Commuter Pass (JOI18_commuter_pass) Java 11
100 / 100
 1629 ms 63188 KB 
import java.io.*;
import java.util.*;
 
public class commuter_pass {
    static int n, m, s, t, u, v;
    static ArrayList<Edge>[] arr;
    static long[] fromU, fromV;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        StringTokenizer st = new StringTokenizer(file.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(file.readLine());
        s = Integer.parseInt(st.nextToken())-1;
        t = Integer.parseInt(st.nextToken())-1;
        st = new StringTokenizer(file.readLine());
        u = Integer.parseInt(st.nextToken())-1;
        v = Integer.parseInt(st.nextToken())-1;
        arr = new ArrayList[n];
        for (int i=0; i<n; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<m; i++){
            st = new StringTokenizer(file.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken());
            arr[s].add(new Edge(e, c));
            arr[e].add(new Edge(s, c));
        }
        fromU = new long[n];
        fromV = new long[n];
        // First get distances from u and v to all other nodes
        dij(u, fromU);
        dij(v, fromV);
        /*for (long i : fromV){
            System.out.println(i);
        }*/
        long a = dij2(s, t); 
        /* Notice if we take all edges part of a SP from s to all other nodes, and we make them a directed edge, then we form a DAG. The definition of a SP is that there is no cycles, because if there exists a cycle, then it is NOT the SP.
        Then, the tricky part is how to "find the best result over all possible SP". This is where DP on a DAG comes in. 
        Define: dpV[i] = the minimum cost for V to reach any node on the SP from start to i
                dpU[i] = the minimum cost for U to reach any node on the SP from start to i
        Note: dpV[i] and dpU[i] must be referencing the same SP. For example, If we have 2 equal paths 1 and 2 from s to x, node V to path 1 cost 1 and to path 2 cost 2, node U to path 1 cost 5 to path 2 cost 1. We cannot say the dpU[x] = 1 AND dpV[x] = 1, because node U achieves cost 1 with path 1, while node V achieves 1 with path 2. We cannot select both paths. The purpose of the DP is to find the best SP to select such that the value of dpV[end] + dpU[end] is minimial. In the previous example, the best result is dpU[x] = 1 and dpV[x] = 2, such that they both use path 2 and achieve a cost of 3 in total.
        From the observation above, the transition of the DP is:
        From the current node, the min cost to reach node V is min(dpV[parent], to go V directly from curr), same for node U. By looking at the parent, we know that the current node is part of (or the "next node") of the path that dpV[parent] and dpV[parent] is referencing. Thus, to transition, we can either take the best result from dpV[parent] or dpU[parent] (since they are part of the SP path from the start to current node), or go directly to U or V from the current node. 
        if (dpV[i] + dpU[i] < dpV[c])
        dpV[i] = Math.min(dpV[i], Math.min(dpV[parent], fromV[])
        */
        long b = dij2(t, s);
        long ans = Math.min(fromU[v], Math.min(a, b));
        System.out.println(ans);
    }
    public static void dij(int start, long[] dist){
        PriorityQueue<State> pq = new PriorityQueue<>();
        Arrays.fill(dist, (long)1e18);
        pq.add(new State(start, -1, 0));
        dist[start] = 0;
        while (!pq.isEmpty()){
            State curr = pq.poll();
            if (dist[curr.id] != curr.cost){
                continue;
            }
            for (Edge i : arr[curr.id]){
                if (curr.cost + i.cost < dist[i.id]){
                    dist[i.id] = curr.cost + i.cost;
                    pq.add(new State(i.id, curr.id, curr.cost + i.cost));
                }
            }
        }
    }
    public static long dij2(int start, int end){
        long[] dist = new long[n];
        long[] dpU = new long[n];
        long[] dpV = new long[n];
        PriorityQueue<State> pq = new PriorityQueue<>();
        Arrays.fill(dist, (long)1e18);
        Arrays.fill(dpU, (long)1e18);
        Arrays.fill(dpV, (long)1e18);
        boolean[] used = new boolean[n];
        pq.add(new State(start, start, 0));
        dist[start] = 0;
        dpV[start] = fromV[start];
        dpU[start] = fromU[start];
        while (!pq.isEmpty()){
            State curr = pq.poll();
            if (dist[curr.id] != curr.cost){
                continue;
            }
            if (!used[curr.id]){
                used[curr.id] = true;
                for (Edge i : arr[curr.id]){
                    if (curr.cost + i.cost <= dist[i.id]){
                        dist[i.id] = curr.cost + i.cost;
                        pq.add(new State(i.id, curr.id, curr.cost + i.cost));
                    }
                } 
            }
            if (dist[curr.id] == curr.cost){ // Is on SP
                // 2 options, take DP value from parent, or go directly to u or v from curr node. 
                if (dpV[curr.id] + dpU[curr.id] > Math.min(fromV[curr.id], dpV[curr.par]) + Math.min(fromU[curr.id], dpU[curr.par])){
                    dpV[curr.id] =  Math.min(fromV[curr.id], dpV[curr.par]);
                    dpU[curr.id] =  Math.min(fromU[curr.id], dpU[curr.par]);
                }
            }
        }
        return dpV[end] + dpU[end];
    }
    static class State implements Comparable<State>{
        int id, par;
        long cost;
        public State(int id, int par, long cost){
            this.id = id;
            this.par = par;
            this.cost = cost;
        }
        public int compareTo(State o){
            return Long.compare(this.cost, o.cost);
        } 
    }
    static class Edge{
        int id;
        long cost;
        public Edge(int id, long cost){
            this.id = id;
            this.cost = cost;
        }
    }
}

Compilation message

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 48772 KB Output is correct
2 Correct 1432 ms 50776 KB Output is correct
3 Correct 1512 ms 47508 KB Output is correct
4 Correct 1516 ms 52704 KB Output is correct
5 Correct 1487 ms 50772 KB Output is correct
6 Correct 1459 ms 47164 KB Output is correct
7 Correct 1366 ms 48120 KB Output is correct
8 Correct 1439 ms 48376 KB Output is correct
9 Correct 1476 ms 46752 KB Output is correct
10 Correct 1362 ms 50068 KB Output is correct
11 Correct 993 ms 39572 KB Output is correct
12 Correct 1436 ms 49324 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 48480 KB Output is correct
2 Correct 1485 ms 54696 KB Output is correct
3 Correct 1434 ms 54664 KB Output is correct
4 Correct 1447 ms 54412 KB Output is correct
5 Correct 1433 ms 53464 KB Output is correct
6 Correct 1414 ms 46720 KB Output is correct
7 Correct 1471 ms 53496 KB Output is correct
8 Correct 1481 ms 54108 KB Output is correct
9 Correct 1441 ms 53828 KB Output is correct
10 Correct 1464 ms 54728 KB Output is correct
11 Correct 1010 ms 40604 KB Output is correct
12 Correct 1431 ms 47064 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 17168 KB Output is correct
2 Correct 119 ms 9160 KB Output is correct
3 Correct 118 ms 9016 KB Output is correct
4 Correct 547 ms 19372 KB Output is correct
5 Correct 523 ms 16784 KB Output is correct
6 Correct 215 ms 12068 KB Output is correct
7 Correct 240 ms 12688 KB Output is correct
8 Correct 284 ms 12988 KB Output is correct
9 Correct 223 ms 12264 KB Output is correct
10 Correct 486 ms 16776 KB Output is correct
11 Correct 93 ms 8592 KB Output is correct
12 Correct 101 ms 8576 KB Output is correct
13 Correct 113 ms 8596 KB Output is correct
14 Correct 188 ms 11540 KB Output is correct
15 Correct 209 ms 12104 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 48772 KB Output is correct
2 Correct 1432 ms 50776 KB Output is correct
3 Correct 1512 ms 47508 KB Output is correct
4 Correct 1516 ms 52704 KB Output is correct
5 Correct 1487 ms 50772 KB Output is correct
6 Correct 1459 ms 47164 KB Output is correct
7 Correct 1366 ms 48120 KB Output is correct
8 Correct 1439 ms 48376 KB Output is correct
9 Correct 1476 ms 46752 KB Output is correct
10 Correct 1362 ms 50068 KB Output is correct
11 Correct 993 ms 39572 KB Output is correct
12 Correct 1436 ms 49324 KB Output is correct
13 Correct 1449 ms 48480 KB Output is correct
14 Correct 1485 ms 54696 KB Output is correct
15 Correct 1434 ms 54664 KB Output is correct
16 Correct 1447 ms 54412 KB Output is correct
17 Correct 1433 ms 53464 KB Output is correct
18 Correct 1414 ms 46720 KB Output is correct
19 Correct 1471 ms 53496 KB Output is correct
20 Correct 1481 ms 54108 KB Output is correct
21 Correct 1441 ms 53828 KB Output is correct
22 Correct 1464 ms 54728 KB Output is correct
23 Correct 1010 ms 40604 KB Output is correct
24 Correct 1431 ms 47064 KB Output is correct
25 Correct 544 ms 17168 KB Output is correct
26 Correct 119 ms 9160 KB Output is correct
27 Correct 118 ms 9016 KB Output is correct
28 Correct 547 ms 19372 KB Output is correct
29 Correct 523 ms 16784 KB Output is correct
30 Correct 215 ms 12068 KB Output is correct
31 Correct 240 ms 12688 KB Output is correct
32 Correct 284 ms 12988 KB Output is correct
33 Correct 223 ms 12264 KB Output is correct
34 Correct 486 ms 16776 KB Output is correct
35 Correct 93 ms 8592 KB Output is correct
36 Correct 101 ms 8576 KB Output is correct
37 Correct 113 ms 8596 KB Output is correct
38 Correct 188 ms 11540 KB Output is correct
39 Correct 209 ms 12104 KB Output is correct
40 Correct 1562 ms 54664 KB Output is correct
41 Correct 1414 ms 50176 KB Output is correct
42 Correct 1396 ms 49104 KB Output is correct
43 Correct 997 ms 43360 KB Output is correct
44 Correct 988 ms 43324 KB Output is correct
45 Correct 1458 ms 53548 KB Output is correct
46 Correct 1470 ms 53752 KB Output is correct
47 Correct 1619 ms 57684 KB Output is correct
48 Correct 1152 ms 42344 KB Output is correct
49 Correct 1629 ms 63188 KB Output is correct
50 Correct 1475 ms 52316 KB Output is correct
51 Correct 1532 ms 55556 KB Output is correct