oj.uz

Submission #470362

# Submission time Handle Problem Language Result Execution time Memory
470362 2021-09-03T15:23:51 Z rainliofficial Commuter Pass (JOI18_commuter_pass) Java 11
100 / 100
 1646 ms 64240 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];
        dij(u, fromU);
        dij(v, fromV);
        /*for (long i : fromV){
            System.out.println(i);
        }*/
        long a = dij2(s, t);
        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 1535 ms 48580 KB Output is correct
2 Correct 1546 ms 50452 KB Output is correct
3 Correct 1517 ms 47408 KB Output is correct
4 Correct 1600 ms 52536 KB Output is correct
5 Correct 1534 ms 50500 KB Output is correct
6 Correct 1464 ms 47240 KB Output is correct
7 Correct 1498 ms 47980 KB Output is correct
8 Correct 1441 ms 48164 KB Output is correct
9 Correct 1469 ms 46148 KB Output is correct
10 Correct 1529 ms 49796 KB Output is correct
11 Correct 1078 ms 39216 KB Output is correct
12 Correct 1496 ms 50740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 48560 KB Output is correct
2 Correct 1515 ms 54328 KB Output is correct
3 Correct 1460 ms 54656 KB Output is correct
4 Correct 1482 ms 54308 KB Output is correct
5 Correct 1466 ms 53600 KB Output is correct
6 Correct 1437 ms 46624 KB Output is correct
7 Correct 1480 ms 53728 KB Output is correct
8 Correct 1509 ms 53968 KB Output is correct
9 Correct 1484 ms 53480 KB Output is correct
10 Correct 1512 ms 54496 KB Output is correct
11 Correct 1004 ms 40620 KB Output is correct
12 Correct 1499 ms 50520 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 17264 KB Output is correct
2 Correct 121 ms 9136 KB Output is correct
3 Correct 118 ms 9232 KB Output is correct
4 Correct 542 ms 18856 KB Output is correct
5 Correct 527 ms 16420 KB Output is correct
6 Correct 216 ms 11912 KB Output is correct
7 Correct 246 ms 12524 KB Output is correct
8 Correct 286 ms 13024 KB Output is correct
9 Correct 218 ms 12156 KB Output is correct
10 Correct 496 ms 16340 KB Output is correct
11 Correct 96 ms 8680 KB Output is correct
12 Correct 101 ms 8604 KB Output is correct
13 Correct 112 ms 8796 KB Output is correct
14 Correct 182 ms 11664 KB Output is correct
15 Correct 201 ms 11948 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 48580 KB Output is correct
2 Correct 1546 ms 50452 KB Output is correct
3 Correct 1517 ms 47408 KB Output is correct
4 Correct 1600 ms 52536 KB Output is correct
5 Correct 1534 ms 50500 KB Output is correct
6 Correct 1464 ms 47240 KB Output is correct
7 Correct 1498 ms 47980 KB Output is correct
8 Correct 1441 ms 48164 KB Output is correct
9 Correct 1469 ms 46148 KB Output is correct
10 Correct 1529 ms 49796 KB Output is correct
11 Correct 1078 ms 39216 KB Output is correct
12 Correct 1496 ms 50740 KB Output is correct
13 Correct 1530 ms 48560 KB Output is correct
14 Correct 1515 ms 54328 KB Output is correct
15 Correct 1460 ms 54656 KB Output is correct
16 Correct 1482 ms 54308 KB Output is correct
17 Correct 1466 ms 53600 KB Output is correct
18 Correct 1437 ms 46624 KB Output is correct
19 Correct 1480 ms 53728 KB Output is correct
20 Correct 1509 ms 53968 KB Output is correct
21 Correct 1484 ms 53480 KB Output is correct
22 Correct 1512 ms 54496 KB Output is correct
23 Correct 1004 ms 40620 KB Output is correct
24 Correct 1499 ms 50520 KB Output is correct
25 Correct 548 ms 17264 KB Output is correct
26 Correct 121 ms 9136 KB Output is correct
27 Correct 118 ms 9232 KB Output is correct
28 Correct 542 ms 18856 KB Output is correct
29 Correct 527 ms 16420 KB Output is correct
30 Correct 216 ms 11912 KB Output is correct
31 Correct 246 ms 12524 KB Output is correct
32 Correct 286 ms 13024 KB Output is correct
33 Correct 218 ms 12156 KB Output is correct
34 Correct 496 ms 16340 KB Output is correct
35 Correct 96 ms 8680 KB Output is correct
36 Correct 101 ms 8604 KB Output is correct
37 Correct 112 ms 8796 KB Output is correct
38 Correct 182 ms 11664 KB Output is correct
39 Correct 201 ms 11948 KB Output is correct
40 Correct 1567 ms 56232 KB Output is correct
41 Correct 1464 ms 51268 KB Output is correct
42 Correct 1448 ms 50540 KB Output is correct
43 Correct 989 ms 43380 KB Output is correct
44 Correct 980 ms 43424 KB Output is correct
45 Correct 1483 ms 54232 KB Output is correct
46 Correct 1494 ms 54288 KB Output is correct
47 Correct 1646 ms 58904 KB Output is correct
48 Correct 1137 ms 42060 KB Output is correct
49 Correct 1626 ms 64240 KB Output is correct
50 Correct 1474 ms 52872 KB Output is correct
51 Correct 1550 ms 55876 KB Output is correct