不想套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); } }