Submission #397028

#	Time	Username	Problem	Language	Result	Execution time	Memory
397028		SGSRainbowDragon	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	2098 ms	34016 KiB

commuter_pass

import java.util.*;
import java.io.*;

public class commuter_pass {

    static long[] distance;
    static boolean[] visited;
    static ArrayList<Edge>[] edges;
    static int n;
    static ArrayList<Integer> path;

    public static void main(String[] args) throws IOException{

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader input = new BufferedReader(new FileReader("cp.in"));
        // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("cp.out")));

        StringTokenizer st = new StringTokenizer(input.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(input.readLine());
        int s = Integer.parseInt(st.nextToken()) - 1;
        int t = Integer.parseInt(st.nextToken()) - 1;

        st = new StringTokenizer(input.readLine());
        int u = Integer.parseInt(st.nextToken()) - 1;
        int v = Integer.parseInt(st.nextToken()) - 1;

        distance = new long[n];
        visited = new boolean[n];

        edges = new ArrayList[n];
        for (int i = 0; i < n; i++)
        {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < m; i++)
        {
            st = new StringTokenizer(input.readLine());
            int one = Integer.parseInt(st.nextToken()) - 1;
            int two = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());
            Edge edge = new Edge(weight, one, two);
            edges[one].add(edge);
            edges[two].add(edge);
        }

        getShortestPath(s, t);

        // System.out.println(distance[t]);

        getPath(s, t);

        // printPath();

        getShortestPath(u, v);

        System.out.println(distance[v]);
    }

    static void getShortestPath(int start, int end) {

        Arrays.fill(distance, Long.MAX_VALUE);
        Arrays.fill(visited, false);

        int current = start;
        distance[current] = 0;

        while (!visited[end]) {

            visited[current] = true;
            for (Edge edge : edges[current])
            {
                int other = edge.getOther(current);
                if (distance[other] > (distance[current] + edge.weight))
                {
                    distance[other] = distance[current] + edge.weight;
                }
            }

            current = getNext();
        }
    }

    static int getNext() {

        long value = Long.MAX_VALUE;
        int index = -1;

        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && distance[i] < value)
            {
                value = distance[i];
                index = i;
            }
        }

        return index;
    }

    static void getPath(int start, int end) {

        path = new ArrayList<>();

        long pw = distance[end];
        int current = end;
        path.add(end+1);

        while (pw > 0)
        {
            for (Edge edge : edges[current])
            {
                int other = edge.getOther(current);
                if (edge.weight == (distance[current] - distance[other]))
                {
                    pw = pw - edge.weight;
                    edge.weight = 0;
                    current = other;
                    path.add(current+1);
                    break;
                }
            }
        }
    }

    static void printPath() {

        for (int i : path) {
            System.out.print(i + " - ");
        }
        System.out.println();
    }

    static class Edge {

        int weight;
        int one;
        int two;

        public Edge (int weight, int one, int two) {
            this.weight = weight;
            this.one = one;
            this.two = two;
        }

        public int getOther (int current) {
            return current == this.one ? this.two : this.one;
        }
    }
}

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: 0 / 24
• Subtask 4: 0 / 45