Submission #347939

#	Time	Username	Problem	Language	Result	Execution time	Memory
347939		TruaShamu	Commuter Pass (JOI18_commuter_pass)	Java	24 / 100	2092 ms	80152 KiB

commuter_pass

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class commuter_pass {
    public static long ans;
    public static ArrayList<Integer[]>[] adj;
    public static boolean[] visited = new boolean[100001];
    public static long[] du = new long[100001];
    public static long[] dv = new long[100001];
    public static long[] ds = new long[100001];
    public static long[][] dp = new long[2][100001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int U = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());


        adj = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj[a].add(new Integer[]{b, c}); //[[NODE, WEIGHT]]
            adj[b].add(new Integer[]{a, c});
        }


        dijkstra1(U, du);

        dijkstra1(V, dv);

        ans = du[V];

        djikstra2(S, T);
        djikstra2(T, S);
        System.out.println(ans);


    }


    public static void dijkstra1(int start, long[] arr) {
        Arrays.fill(visited, false);

        PriorityQueue<pair> pq = new PriorityQueue<>();
        pq.add(new pair(0, start));
        while (!pq.isEmpty()) {
            long c;
            int node;
            pair cur = pq.poll();
            c = cur.dist;
            node = cur.node;

            if (!visited[node]) {
                arr[node] = c;
                visited[node] = true;
                for (Integer[] i : adj[node]) {
                    pq.add(new pair(c + i[1], i[0]));
                }
            }
        }
    }

    //2ND ROUND
    public static void djikstra2(int source, int sink) {
        Arrays.fill(dp[0], Long.MAX_VALUE / 2);
        Arrays.fill(dp[1], Long.MAX_VALUE / 2);
        Arrays.fill(visited, false);
        PriorityQueue<item> pq = new PriorityQueue<>();
        pq.add(new item(0, source, 0));

        dp[0][0] = dp[1][0] = Long.MAX_VALUE / 2;
        while (!pq.isEmpty()) {
            item cur = pq.poll();
            if (!visited[cur.node]) {
                visited[cur.node] = true;
                ds[cur.node] = cur.cost;
                dp[0][cur.node] = Long.min(du[cur.node], dp[0][cur.par]);
                dp[1][cur.node] = Long.min(dv[cur.node], dp[1][cur.par]);
                for (Integer[] oEdge : adj[cur.node]) {
                    pq.add(new item(cur.cost + oEdge[1], oEdge[0], cur.node));
                }
            } else if (cur.cost == ds[cur.node]) {
                if (Long.min(du[cur.node], dp[0][cur.par]) + Long.min(dv[cur.node], dp[1][cur.par]) <= dp[0][cur.node] + dp[1][cur.node]) {
                    dp[0][cur.node] = Long.min(du[cur.node], dp[0][cur.par]);
                    dp[1][cur.node] = Long.min(dv[cur.node], dp[1][cur.par]);
                }
            }
        }
        ans = Long.min(ans, dp[0][sink] + dp[1][sink]);
    }

}

class pair implements Comparable<pair> {
    public long dist;
    public int node;

    public pair(long dist, int node) {
        this.dist = dist;
        this.node = node;
    }

    public String toString() {
        return "A: " + this.dist + " B: " + this.node;
    }

    public int compareTo(pair other) {
        if (this.dist != other.dist) {
            return Long.compare(this.dist, other.dist);
        }
        return Long.compare(this.node, other.node);

    }
}

class item implements Comparable<item> {
    public long cost;
    public int node, par;

    public item(long cost, int node, int par) {
        this.cost = cost;
        this.node = node;
        this.par = par;
    }

    public int compareTo(item other) {

        return Long.compare(this.cost, other.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