Submission #470359

#	Time	Username	Problem	Language	Result	Execution time	Memory
470359		rainliofficial	Commuter Pass (JOI18_commuter_pass)	Java	24 / 100	1707 ms	58136 KiB

commuter_pass

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)1e12);
        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)1e12);
        Arrays.fill(dpU, (long)1e12);
        Arrays.fill(dpV, (long)1e12);
        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 (stderr)

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

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45