nc3856

不想套C++高精的同学可以用java大数+各种最短路算法实现
这里用了dijkstra

// package nc3856;

import java.io.*;
import java.math.BigInteger;
import java.util.PriorityQueue;

public class Main {

    static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int n, m, head[], tot;
    static Edge[] G;
    static PriorityQueue<Point> pq = new PriorityQueue<>();
    static BigInteger dis[], inf, two, p;
    static boolean vis[];
    static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m =  nextInt();
        init();
        for(int i = 1, u, v ; i <= m ; ++i) {
            u = nextInt();
            v = nextInt();
            addEdge(u,v,inf);
            addEdge(v,u,inf);
            inf = inf.multiply(two);
        }
        dijkstra();
        for(int i = 1 ; i < n ; ++i) {
            if(dis[i].compareTo(inf)==0) {
                ans.append("-1\n");
                continue;
            }
            ans.append(dis[i].mod(p).toString()).append('\n');
        }
        System.out.print(ans);
    }

    public static void dijkstra() {
        for(int i = 1 ; i < n ; ++i) dis[i] = new BigInteger(inf.toByteArray());
        dis[0] = new BigInteger("0");
        pq.add(new Point(0,dis[0]));
        while(!pq.isEmpty()) {
            int np = pq.poll().p;
            if(vis[np]) continue;
            vis[np] = true;
            for(int i = head[np], to ; i != 0 ; i = G[i].next) {
                to = G[i].to;
                if(!vis[to]&&dis[to].compareTo(new BigInteger(dis[np].add(G[i].val).toByteArray()))==1) {
                    dis[to] = new BigInteger(dis[np].add(G[i].val).toByteArray());
                    pq.add(new Point(to,dis[to]));
                }
            }
        }
    }

    public static int nextInt() throws IOException {
        cin.nextToken();
        return (int)cin.nval;
    }

    public static void addEdge(int u, int v, BigInteger val) {
        G[++tot].np = u;
        G[tot].to = v;
        G[tot].val = new BigInteger(val.toByteArray());
        G[tot].next = head[u];
        head[u] = tot;
    }

    public static void init() {
        G = new Edge[(m<<1)|1];
        for(int i = 1 ; i <= (m<<1) ; ++i) G[i] = new Edge();
        head = new int[n+1];
        dis = new BigInteger[n+1];
        inf = new BigInteger("1");
        two = new BigInteger("2");
        vis = new boolean[n+1];
        p = new BigInteger("100000");
    }

}

class Edge{
    int np, to, next;
    BigInteger val;
}

class Point implements Comparable<Point>{
    int p;
    BigInteger dis;
    public Point(int p, BigInteger dis) {
        this.p = p;
        this.dis = dis;
    }

    @Override
    public int compareTo(Point o) {
        return this.dis.compareTo(o.dis);
    }
}