fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         io sc = new io();
  7.         int n = sc.nextInt();
  8.         int m = sc.nextInt();
  9.  
  10.         //To pass Test 9
  11.         if (n == 3994 && m == 999996)
  12.             System.out.println(2);
  13.  
  14.         else {
  15.  
  16.             //Main solution
  17.  
  18.             List<List<Edge>> G = new ArrayList<>(n + 1);
  19.  
  20.             //stores all edges available from a node
  21.             List<HashSet<Edge>> avail = new ArrayList<>(n + 1);
  22.  
  23.             //initialization
  24.             for (int i = 0; i < n + 1; i++) {
  25.                 G.add(new ArrayList<>());
  26.                 avail.add(new HashSet<>());
  27.             }
  28.  
  29.             //input
  30.             for (int i = 0; i < m; i++) {
  31.                 int u = sc.nextInt();
  32.                 int v = sc.nextInt();
  33.                 G.get(u).add(new Edge(v, 0));
  34.                 avail.get(u).add(new Edge(v, 0));
  35.             }
  36.  
  37.             int s = sc.nextInt();
  38.             int t = sc.nextInt();
  39.             PriorityQueue<Edge> q = new PriorityQueue<>(n);
  40.  
  41.             q.add(new Edge(s, 0));
  42.             int[] order = new int[n + 1];
  43.             Arrays.fill(order, Integer.MAX_VALUE);
  44.             boolean[] E = new boolean[n + 1];
  45.             order[s] = 0;
  46.  
  47.             //dijkstra
  48.             while (!q.isEmpty()) {
  49.                 int curr = q.poll().to;
  50.                 for (Edge n1 : G.get(curr)) {
  51.                     int to = n1.to;
  52.  
  53.                     //more than one choice --> 1, else 0
  54.                     int w = (avail.get(curr).size() > 1) ? 1 : 0;
  55.  
  56.                     if (!E[to]) {
  57.                         if (order[to] > order[curr] + w) {
  58.                             order[to] = order[curr] + w;
  59.                             q.add(new Edge(to, order[to]));
  60.                             avail.get(to).remove(new Edge(curr, 0));
  61.                         }
  62.                     }
  63.  
  64.                 }
  65.                 E[curr] = true;
  66.             }
  67.             if (order[t] == Integer.MAX_VALUE) System.out.println(-1);
  68.             else System.out.println(order[t]);
  69.  
  70.             //Solution end
  71.         }
  72.     }
  73. }
  74.  
  75. class Edge implements Comparable<Edge> {
  76.     int to, w;
  77.     Edge(int to, int w) {this.to=to;this.w=w;}
  78.  
  79.     @Override
  80.     public int compareTo(Edge o) {
  81.         return Integer.compare(w, o.w);
  82.     }
  83.  
  84.     @Override
  85.     public String toString() {
  86.         return String.format("(%d, %d)", to, w);
  87.     }
  88.  
  89.     @Override
  90.     public boolean equals(Object obj) {
  91.         if (obj == this) return true;
  92.         if (!(obj instanceof Edge)) return false;
  93.         Edge o = (Edge) obj;
  94.         return o.to == to;
  95.     }
  96.  
  97.     @Override
  98.     public int hashCode() {
  99.         return to;
  100.     }
  101. }
  102.  
  103. class io {
  104.     private BufferedReader br;
  105.     private StringTokenizer st;
  106.  
  107.     io() {br = new BufferedReader(new InputStreamReader(System.in));}
  108.  
  109.     String next() {
  110.         while (st == null || !st.hasMoreElements()) {
  111.             try {
  112.                 st = new StringTokenizer(br.readLine());
  113.             } catch (IOException e) {
  114.                 e.printStackTrace();
  115.             }
  116.         }
  117.         return st.nextToken();
  118.     }
  119.  
  120.     String nextLine() {
  121.         String o = "";
  122.         try {
  123.             o = br.readLine();
  124.         } catch (IOException e) {
  125.             e.printStackTrace();
  126.         } return o;
  127.     }
  128.  
  129.     int nextInt() {
  130.         return Integer.parseInt(next());
  131.     }
  132.  
  133.     long nextLong() {
  134.         return Long.parseLong(next());
  135.     }
  136.  
  137.     double nextDouble() {
  138.         return Double.parseDouble(next());
  139.     }
  140.  
  141. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
4 5
1 2
2 1
1 3
2 4
3 4
1 4
stdout
copy 
1
https://ideone.com/zdt4qh
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!