图论之最短路径数目

package com.zhang.reflection.面试.算法模版.图.最短路径数目;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
public class 最短路径数目{
    static class Edge{
        private int from;
        private int to;
        private int weight;
        public Edge(int from,int to){
            this.from=from;
            this.to=to;
        }
    }
    private static int n;
    private static int m;
    private static ArrayList<Edge>[] nodes;
    private static boolean[] curNode;
    private static int[] count;
    private static int[] dis;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st=new StreamTokenizer(br);
        st.nextToken();n=(int)st.nval;
        st.nextToken();m=(int)st.nval;
        nodes=new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            nodes[i]=new ArrayList<Edge>();
        }
        curNode=new boolean[n+1];
        count=new int[n+1];
        dis=new int[n+1];
        for(int i=0;i<m;i++){
            st.nextToken();int from=(int)st.nval;
            st.nextToken();int to=(int)st.nval;
            Edge edge1=new Edge(from,to);
            Edge edge2=new Edge(to,from);
            nodes[from].add(edge1);
            nodes[to].add(edge2);
        }
        dfs();
        for(int i=1;i<=n;i++){
            if(count[i]==Integer.MAX_VALUE){
                System.out.println(0);
            }else{
                System.out.println(count[i]%100003);
            }
        }
    }

    private static void dfs() {
        Arrays.fill(dis,Integer.MAX_VALUE);
        Arrays.fill(curNode,false);
        Arrays.fill(count,0);
        curNode[1]=true;
        count[1]=1;
        Deque<Integer> queue=new LinkedList<>();
        queue.offer(1);
        while(!queue.isEmpty()){
            int now= queue.poll();
            for(Edge next:nodes[now]){
                int to=next.to;
                if(!curNode[to]){
                    dis[to]=dis[now]+1;
                    curNode[to]=true;
                    queue.offer(to);
                }
                if(dis[to]==dis[now]+1){
                    count[to]=(count[to]+count[now])%100003;
                }
            }
        }
    }
}