oj.uz

Submission #397016

# Submission time Handle Problem Language Result Execution time Memory
397016 2021-05-01T06:08:34 Z SGSRainbowDragon Commuter Pass (JOI18_commuter_pass) Java 11
0 / 100
 1061 ms 39640 KB 
import java.util.*;
import java.io.*;

public class commuter_pass {

    static long[] distance;
    static ArrayList<Edge>[] edges;

    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());
        int 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];
        Arrays.fill(distance, -1);

        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 w = Integer.parseInt(st.nextToken());
            edges[one].add(new Edge(w, one, two));
            edges[two].add(new Edge(w, two, one));
        }

        distance[s] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (Edge ed : edges[s])
        {
            pq.add(ed);
        }

        while (!pq.isEmpty() && distance[t] < 0)
        {
            Edge edge = pq.poll();

            if (distance[edge.endp] < 0)
            {
                distance[edge.endp] = distance[edge.startp] + edge.weight;

                for (Edge ed : edges[edge.endp])
                {
                    if (distance[ed.endp] < 0)
                    {
                        pq.add(ed);
                    }
                }
            }
        }

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

        // ArrayList<Integer> path = new ArrayList<Integer>();
        long pw = distance[t];
        int cur = t;
        // path.add(t+1);

        while (pw > 0)
        {
            for (Edge ed : edges[cur])
            {
                if (ed.weight == (distance[cur] - distance[ed.endp]))
                {
                    pw = pw - ed.weight;
                    ed.weight = 0;

                    for (Edge oe : edges[ed.endp])
                    {
                        if (oe.endp == cur)
                        {
                            oe.weight = 0;
                            break;
                        }
                    }

                    cur = ed.endp;
                    break;
                }
            }
        }

        // printPath(path);

        Arrays.fill(distance, -1);

        distance[u] = 0;

        pq.clear();
        for (Edge ed : edges[u])
        {
            pq.add(ed);
        }

        while (!pq.isEmpty() && distance[v] < 0)
        {
            Edge edge = pq.poll();

            if (distance[edge.endp] < 0)
            {
                distance[edge.endp] = distance[edge.startp] + edge.weight;

                for (Edge ed : edges[edge.endp])
                {
                    if (distance[ed.endp] < 0)
                    {
                        pq.add(ed);
                    }
                }
            }
        }

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

    static void printPath(ArrayList<Integer> path) {

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

    static class Edge implements Comparable<Edge> {

        int weight;
        int startp;
        int endp;

        public Edge (int w, int sp, int ep) {
            this.weight = w;
            this.startp = sp;
            this.endp = ep;
        }

        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }
}

Compilation message

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 956 ms 39244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 39332 KB Output is correct
2 Correct 1061 ms 39640 KB Output is correct
3 Correct 1008 ms 39376 KB Output is correct
4 Correct 954 ms 39372 KB Output is correct
5 Correct 1012 ms 39584 KB Output is correct
6 Incorrect 1000 ms 39380 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 410 ms 16272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 956 ms 39244 KB Output isn't correct
2 Halted 0 ms 0 KB -