Submission #4029235

---

Source Code Expand

import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        int N=sc.nextInt();
        int a=sc.nextInt(),b=sc.nextInt();
        int M=sc.nextInt();
        int mod=1000000007;
        long[] min=new long[N+1];
        for (int i = 0; i <= N; i++) min[i] = mod;
        min[a]=0;
        long[] count=new long[N+1];
        count[a]=1;
        int[] node=new int[N+1];
        LinkedList<Integer>[] edge=new LinkedList[N+1];
        for(int i=0;i<N+1;i++)edge[i]=new LinkedList<>();
        for (int i = 0; i <M; i++) {
            int x=sc.nextInt(),y=sc.nextInt();
            edge[x].add(y);
            edge[y].add(x);
        }
        Queue<Integer> q=new ArrayDeque<>();
        q.add(a);
        Queue<Long> dist=new ArrayDeque<>();
        dist.add(0l);
        while (q.size()>0){
            int vertex=q.poll();
            long d=dist.poll();
            min[vertex]=min(min[vertex],d);
            for (Integer child:edge[vertex]){
                edge[child].remove((Integer)vertex);
                q.add(child);
                dist.add(d+1);
            }
        }
        q.add(a);
        dist.add(0l);
        while (q.size()>0){
            int vertex=q.poll();
            long d=dist.poll();
            if(node[vertex]==0) {
                for (Integer child : edge[vertex]) {
                    if(min[child]==d+1)count[child] = (count[child] + count[vertex]) % mod;
                    if (!q.contains(child)) {
                        q.add(child);
                        dist.add(d + 1);
                    }
                }
                node[vertex]=1;
            }
        }
        out.println(count[b]);
    }
}

Submission Info

Compile Error

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

Judge Result