最短路径

最短路径：迪杰斯特拉
大整数：使用字符串存储长度与快速幂取模来模拟

#include<iostream>
(720)#include<algorithm>
#include<queue>
(789)#include<string>
#include<vector>
using namespace std;
const int N = 300;
struct Edge         
{
	
	int end;
	string  length;
	bool operator < (Edge c) const
	{
		return length < c.length;
	}


};
struct Point
{
	int pointnumber;
	string distance;
	Point(int a, string b) : pointnumber(a), distance(b) {}
	bool operator<(Point c)const
	{
		return distance > c.distance;
	
	}

};

string dist[N];       //源点到其他点的距离
int cost[N];
priority_queue<Point>   mindis;     //用于筛选最短距离的点
string chart(int k)    //     2的k次方
{
	string s;
	s.insert(0, 502, '0');
	s[s.size()-1-k] = '1';
	return s;
}
string adds(string a, string b)    //字符串加法
{
	string s;
	for (int i = 0; i < a.size(); i++)
		s.append(1, (a[i] - '0' + b[i] - '0')+'0');

	return s;
}
int atois(string s)        //快速幂取模
{
	int ans=0;
	int front = 1;
	for (int i = s.size()-1; i>=0; i--)
	{
		if (s[i] == '1')
		{
			ans += front;
			ans = ans % 100000;
		}
	
		front = (front * 2) % 100000;
	
	}
	return ans;

}
void Dijkstra(int z,vector<Edge>graph[N])     //最短路径
{
	dist[z][0] = '0';
	mindis.push(Point(z,dist[z]));
	while (!mindis.empty())
	{
		int k = mindis.top().pointnumber;
		mindis.pop();
		for (int i =0 ; i < graph[k].size(); i++)
		{
			string old = dist[graph[k][i].end];
			string news = adds(dist[k] , graph[k][i].length);
			if (old  > news )    
			{
				dist[graph[k][i].end] = news;
				mindis.push(Point(graph[k][i].end, dist[graph[k][i].end]));
			}
		
		}
	}
}

void Initial()
{
	
	for (int i = 0; i < N; i++)
	{
		dist[i] = chart(501);
		
	}
	dist[0][0] = '0';
	
}
int main()                                       
{
	int n, m;
	int a, b;
	while (cin>>n>>m)
	{
		Initial();
		vector<Edge> graph[N];
		for (int i = 0; i < m; i++)
		{
			Edge x;
			cin >> a>>b;
			x.end = b;
			x.length = chart(i);
			graph[a].push_back(x);
			x.end = a;
			graph[b].push_back(x);
		    
		}
		Dijkstra(0, graph);
		for (int i = 1; i < n; i++)
		{
			if (dist[i] == chart(501)) cout << "-1" << endl;
			else cout << atois(dist[i])<<endl;
		}
		
	}

}

//AC代码：
import java.math.*;
import java.util.*;

public class Main {
    static String INF="";
    static BigInteger [][]G=new BigInteger[105][105];
    static BigInteger MOD=new BigInteger("100000"),Base=new BigInteger("2");
    public static void main(String [] args){
        int n,m,i,j,k,a,b;
        for(i=0;i<160;i++) INF+="9";
        for(i=0;i<105;i++)
            for(j=0;j<105;j++)
                if(i!=j) G[i][j]=new BigInteger(INF);
                else G[i][j]=new BigInteger("0");
        Scanner in=new Scanner(System.in);
        n=in.nextInt(); m=in.nextInt();
        for(k=0;k<m;k++){
            a=in.nextInt(); b=in.nextInt();
            if(!G[a][b].toString().equals(INF)) continue;
            G[a][b]=new BigInteger(Base.pow(k).toString());
            G[b][a]=new BigInteger(Base.pow(k).toString());
        }
        for(k=0;k<n;k++)
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    if(G[i][j].compareTo(G[i][k].add(G[k][j]))>0)
                        G[i][j]=G[i][k].add(G[k][j]);
        for(i=1;i<n;i++) 
            if(G[0][i].toString().equals(INF))
                System.out.println("-1");
            else
                System.out.println(G[0][i].mod(MOD));
    }
}//100个点  直接弗洛伊德就能AC

#include <stdio.h>
//#include <conio.h>
#define printf //
//单源最短路径 迪杰斯特拉算法
//集合S保存最短路径上的节点,V表示待求最短路径的节点,d[i]表示v0到vi的最短路径
//从v0开始
struct Edge{
int v1;
int v2;
int weigh;
}edges[500];
//求第i个道路的长度

//表示道路长度
struct BigInteger{
int digit[500];
int size;
}t[100];//v0到vi节点的距离
//大整数比较 用于比较距离
int comp(BigInteger b1,BigInteger b2){
if(b1.size>b2.size) return 1;
else if(b1.size==b2.size){
for(int i=b1.size-1;i>=0;i--){
if(b1.digit[i]>b2.digit[i])
return 1;
else if(b1.digit[i]<b2.digit[i]) return -1;
}
return 0;
}
else return -1;
int w(int i){
int res=1;
while(i>0){
res*=2;
res%=100000;
i--;
}
return res;
void p(BigInteger b){
printf("( size:%d )",b.size);
for(int i=0;i<b.size;i++)
if(b.digit[i]==1)
printf("%d,",i);
printf("\n");
}
int d[101];//v0到vi的最短路径  判断
int x[101];//存放实际长度
int S[101];//s[i]==1表示已求得v0到vi的最短路径
int main(){
//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);

int N,M;
while(~scanf("%d %d",&N,&M)){
for(int i=0;i<N;i++){
d[i]=-1;
S[i]=0;
x[i]=-1;
for(int j=0;j<500;j++)
t[i].digit[j]=0;
t[i].digit[499]=1;
t[i].size=500;

}
for(int i=0;i<M;i++){
scanf("%d %d",&edges[i].v1,&edges[i].v2);
edges[i].weigh=i;//k代表2的k次方
//printf("第%d条道路长度为%d\n",i,w(i));

//t表示vi到v0的最短距离 或经由K中某顶点到达vi的最小距离；
if(edges[i].v2==0){
t[edges[i].v1].size=i+1;
t[edges[i].v1].digit[i]=1;
t[edges[i].v1].digit[499]=0;
}
if(edges[i].v1==0){
t[edges[i].v2].size=i+1;
t[edges[i].v2].digit[i]=1;
t[edges[i].v2].digit[499]=0;
}
}
printf("\n");
d[0]=0;S[0]=1;x[0]=0;t[0].digit[499]=0;t[0].size=0;
int k=0;
for(int j=0;j<N-1;j++){
//if(k==2) break;
k++;
//S中只有0
int next_v=0;
BigInteger min;
for(int i=0;i<500;i++)
min.digit[i]=0;
min.digit[499]=1;
min.size=500;
int x1,x2,x3;
for(int i=0;i<M;i++){
int v1=edges[i].v1;
int v2=edges[i].v2;
int tem;
//v1在S中 v2不在
if(S[v1]==0&&S[v2]==1){
tem=v1;
v1=v2;
v2=tem;
}
//找最小值
if(S[v1]==1&&S[v2]==0){
printf("此边由%d到%d 权值为%d \n", v1,v2, edges[i].weigh);
//    t[v2][edges.weigh]=1;
//int d_v2=d[v1]+edges[i].weigh;
BigInteger temp = t[v1];
printf("由v0到(v1:v%d)的距离为",v1);
p(t[v1]);

temp.digit[edges[i].weigh]=1;
//
printf("由v0到(v2:v%d)距离为",v2);
p(temp);
if(comp(t[v2],temp)==1){
printf("由v0到v%d的距离大于由v0到V%d,再由v%d到v%d的距离,修改数据\n",v2,v1,v2);
t[v2]=temp;
}

if(comp(t[v2],min)==-1){
printf("t[%d]:",v2);
p(t[v2]);
printf("min:");
p(min);
printf("\n");
min=t[v2];
next_v=v2;
x1=v1;
x2=i;
}
}
}
S[next_v]=1;
t[next_v]=min;
//d[next_v]=min;
printf("第%d次,选中%d到%d,权值为%d,距离为%d的边\n", j+1,x1,next_v,edges[x2].weigh,w(edges[x2].weigh));
//printf(")
x[next_v]=(x[x1]+w(edges[x2].weigh))%100000;
printf("将顶点v%d加入S中,v0到v%d",next_v,next_v);
printf("距离为");
p(t[next_v]);
printf("最短路径长度为%d\n\n",x[next_v]);
}
#undef printf
for(int i=1;i<N;i++){
//    if(x[i]==38368) printf("这里%d\n",i);
printf("%d\n",x[i]);

}
//printf("%d\n",x[N-1]);

// printf("%d\n",w(54));


}
// fclose(stdin);
//getch();

return 0;
}

重边是真的坑死人。。天坑。。。。。

//天坑，这题有重复输入，检测到第二次输入时，不应该向图中添加路径
//用并查集的板子来解决重复输入的问题，两个结点已经是联通的，就不要再继续覆盖路径了

#include <iostream>
(720)#include <vector>
#include <queue>
(789)#include <algorithm>//包含fill函数
#include <cstring>//包含memset函数
(2978)#include <climits>//包含INT_MAX

using namespace std;

const int MAXN = 101;
const int INF = INT_MAX;

struct Edge//源点即为下标
{
    int to;//终点下标
    int length;//路径长度
    Edge(int t, int l) : to(t),length(l) {}
};

struct Point
{
    int num;//点的编号
    int dist;//源点到该点的距离
    Point(int n, int d) : num(n),dist(d) {}
    bool operator< (const Point& p) const
    {
        return dist > p.dist;//优先队列输出的是最大的那个，距离越近的优先级应该越高
    }
};

vector<Edge> graph[MAXN];//存储图，graph[i]存储以i为出发结点的所有边
int dis[MAXN];//存储所有结点到目标结点的距离
int father[MAXN];
int height[MAXN];

void initial(int n)
{
    for(int i=0; i<n; i++)
    {
        father[i] = i;
        height[i] = 0;
    }
}

int findroot(int x)
{
    if(x != father[x])
    {
        father[x] = findroot(father[x]);
    }
    return father[x];
}

void Union(int x, int y)
{
    int a = findroot(x);
    int b = findroot(y);
    if(a != b)
    {
        if(height[a] > height[b])
        {
            father[b] = a;
        }
        else if(height[a] < height[b])
        {
            father[a] = b;
        }
        else
        {
            father[b] = a;
            height[a] ++;
        }
    }
    return ;
}

void dijkstra(int s)//输入起点下标
{
    priority_queue<Point> q;//优先级队列
    dis[s] = 0;
    q.push(Point(s,dis[s]));//入队

    while(!q.empty())//队列不空时
    {
        int u = q.top().num;//距离源点最近的点的编号
        q.pop();//队首元素出队

        for(int i=0; i<graph[u].size(); i++)//遍历以u为头结点的所有边
        {
            int v = graph[u][i].to;//当前边的终点
            int d = graph[u][i].length;//u到v的距离
            if(dis[v] > dis[u]+d)//松弛操作，发现距离更近的一条路时，更新路径
            {
                dis[v] = dis[u]+d;
                q.push(Point(v,dis[v]));//将更新后的结点入队
            }
        }
    }
}

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        initial(n);
        fill(dis,dis+n,INF);//初始化距离函数
        memset(graph,0,sizeof(graph));//图初始化

        int length = 1;
        for(int i=0; i<m; i++)
        {
            int from,to;
            cin >> from >> to;

            if(findroot(from) != findroot(to))
            {
                graph[from].push_back(Edge(to,length));//向图内存储路径
                graph[to].push_back(Edge(from,length));
                Union(from,to);
            }
            length = length*2%100000;
        }

        dijkstra(0);

        for(int i=1; i<n; i++)
        {
            if(dis[i] == INF) cout << "-1" << endl;
            else cout << dis[i]%100000 << endl;
        }

    }
    return 0;
}

有坑，有重复输入，重复输入的数据不算数

#include<cstring>
#define maxn 101
#define maxm 501
#define inf 100000
int dis[maxn][maxn];
int d2[maxm];
int n, m,x,y;
int res[maxn];
#pragma warning(disable:4996)
struct node
{
    int pre;
    int w;
    int v;
}q[maxn];
void find2(int index)
{
    if (index == 0)d2[index] = 1;
    else {
        d2[index]=(d2[index - 1] * 2)%inf;
    }
    //return res;
}
int max(int a, int b) {
    return a > b ? a : b;
}
int main()
{
    freopen("in.txt", "r", stdin);
    //memset(v, 0, sizeof(v));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = maxm;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        if(dis[x][y]>=i)
            dis[x][y] = dis[y][x] = i;
    }
    for (int i = 1; i < n; i++)scanf("%d", &res[i]);
    for (int i = 0; i < n; i++) {
        q[i].w = maxm;
        q[i].v = 0;
        q[i].pre = i;
    }
    for(int i=0;i<m;i++)
    {
        find2(i);
    }
    //v[0] = 1;
    q[0].w = 0;
    while (1) {
        int min = maxm;
        int k = -1;
        for (int i = 0; i < n; i++)
        {
            if (!q[i].v) {
                if (q[i].w<min) {
                    k = i;
                    min = q[i].w;
                }
            }
        }
        if (k == -1)break;
        q[k].v = 1;
        for (int i = 0; i < n; i++)
        {
            
            if (!q[i].v && dis[k][i]<maxm && q[i].w > max(min , dis[k][i]))
            {
                q[i].w = max(min, dis[k][i]);
                q[i].pre = k;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (q[i].w == maxm)printf("-1");
        else {
            if (i == 8)
            {
                printf("");
            }
            int l = 0;
            int temp = q[i].pre;
            int now = i;
            while (now != 0)
            {
                l += d2[dis[now][temp]];
                if (l >= inf)l = l%inf;
                now = temp;
                if (now != 0)
                    temp = q[temp].pre;
            }
            printf("%d\n", l);
            //if (res[i] != l)printf("%d\n", i);
        }
        
    }
    return 0;
}

#include <vector>
#include <cstdio>
using namespace std;


struct bigInt{
    int digit[100];
    int size;
    void init(){
        for(int i = 0; i < 100; i++){
            digit[i] = 0;

        }
        size = 0;
    }

    void set(int x){
        init();
        do{
            digit[size++] = x % 10000;
            x /= 10000;
        }while(x != 0);

    }

    bigInt operator *(int x) const{
        bigInt ret;
        ret.init();
        int carry = 0;
        for(int i = 0; i < size;i++){
            int tmp = x*digit[i]+carry;
            carry = tmp/10000;
            tmp = tmp%10000;
            ret.digit[ret.size++] = tmp;
        }
        if(carry != 0){
            ret.digit[ret.size++] = carry;
        }
        return ret;
    }

    bigInt operator +(bigInt x) const{
        bigInt bigint;
        bigint.init();
        int carry = 0;
        for(int i = 0; i < size || i < x.size;i++){
            int tmp = digit[i]+x.digit[i] + carry;
            carry = (digit[i] + x.digit[i])/10000;
            tmp = tmp % 10000;
            bigint.digit[bigint.size++] = tmp;
        }
        if(carry != 0){
            bigint.digit[bigint.size++] = carry;
        }
        return bigint;
        /*for(int i = 0; i < size;i++){
            bigint.digit[bigint.size++] = digit[i];
        }
        int carry = 0;
        int tmp = bigint.digit[bigint.size]+x;
        carry = tmp/10000;
        tmp = tmp % 10000;
        if(carry > 0){
            bigint.digit[bigint.size++] = carry;
        }*/
        return bigint;
    }

    bool operator > (bigInt b){
        if(size != b.size){
            return size > b.size;
        }
        //bool istrue = false;
        for(int i = size-1; i >= 0;i--){
            if(digit[i] != b.digit[i]){
                return digit[i] > b.digit[i];

            }
        }

        return false;

    }

    bool operator != (bigInt b){
        if(size != b.size){
            return true;
        }
        //bool istrue = false;
        for(int i = size-1; i >= 0;i--){
            if(digit[i] != b.digit[i]){
                return true;

            }
        }

        return false;

    }

    int operator %(int x)const{
        int reminder = 0;
        for(int i = size -1; i >= 0; i--){
            int t = (reminder*10000+digit[i])/x;
            int r = (reminder*10000+digit[i])%x;
            reminder = r;
        }
        return reminder;

    }

    void printout(){
        for(int i = size-1; i>= 0; i--){
            if(i != size-1){
                printf("%04d\n",digit[i]);
            }
            else{
                printf("%d\n",digit[i]);
            }
        }
    }


};


struct E{
    int next;
    bigInt c;
};
vector<E> edge[500];
bigInt Dis[500];
bool mark[500];

int main(){
    int n;
    int m;
    scanf("%d %d",&n,&m);
    bigInt big;
    big.init();
    big.set(1);
    for(int i = 0; i < n; i++){
        edge[i].clear();
    }
    //int times  = 1;
    while(m--){
        int a;
        int b;
        int c;
        //if(times == 1)

        scanf("%d %d",&a,&b);
        E tmp;
        tmp.c = big;
        big = big*2;
        tmp.next = b;
        edge[a].push_back(tmp);
        tmp.next = a;
        edge[b].push_back(tmp);

    }
    for(int i = 0; i < n;i++){
        bigInt bigint;
        bigint.init();
        bigint.set(-1);
       Dis[i] = bigint;
        mark[i] = false;
    }
    bigInt zero;
    zero.init();
    zero.set(0);
    Dis[0] = zero;
    mark[0] = true;
    int newP = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < edge[newP].size();j++){
            int t = edge[newP][j].next;
            bigInt c  = edge[newP][j].c;
            if(mark[t] == true){
                continue;
            }

            if(Dis[t].digit[0] == -1 || Dis[t] > Dis[newP]+c){
                Dis[t] = Dis[newP]+c;

            }
        }

        bigInt min;
        min.init();
        for(int i = 0; i < 100;i++){
            min.digit[i] = 9999;
            min.size++;
        }
        bigInt tmp;
        tmp.init();
        tmp.set(-1);
        for(int j = 0; j < n; j++){
            if(mark[j] ==  true){
                continue;
            }
            if(Dis[j] != tmp && min > Dis[j]){
                min = Dis[j];
                newP = j;
            }
        }
        mark[newP] = true;
    }

    for(int i = 1; i < n; i++){
            int x = Dis[i] % 100000;
        cout << x << endl;
    }



    return 0;
}

#include<stdio.h>
#define N 100
int dis[N][N];
int Tree[N];
int FindRoot(int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree[x]);
        return Tree[x];
    }
}
int mod(int x,int y){
    int ret=1;
    while(y--){
        ret=(ret*x)%100000;
    }
    return ret;
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        int i,j,k,a,b,x,y,dist;
        for(i=0;i<n;i++){
            Tree[i]=-1;
            for(j=0;j<n;j++)
                dis[i][j]=-1;
            dis[i][i]=0;
        }
        for(i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            x=FindRoot(a);
            y=FindRoot(b);
            if(x!=y){
                dist=mod(2,i);
                for(j=0;j<n;j++){ 
                    if(x==FindRoot(j)){
                        for(k=0;k<n;k++){ 
                            if(y==FindRoot(k)){
                                dis[j][k]=dis[k][j]=(dis[j][a]+dis[b][k]+dist)%100000;
                            }
                        } 
                    } 
                }
                Tree[y]=x; 
            }
        }
        x=FindRoot(0);
        for(i=1;i<n;i++){
                printf("%d\n",dis[0][i]);
        }
    }
    return 0;
}

	
	

		#include<iostream>
	

	

		using namespace std;
	

	

		int root[105];
	

	

		int distances[105][105];
	

	

		//查找x的根节点
	

	

		int findRootOf(int x){
	

	

		if(root[x]==x)return x;
	

	

		else return root[x]=findRootOf(root[x]);
	

	

		}
	

	

		//计算第k条边的长度(已经mod100000的结果)
	

	

		int getEdgeDist(int k){
	

	

		int dist=1;
	

	

		while(k>0){
	

	

		dist=(dist*2)%100000;
	

	

		--k;
	

	

		}
	

	

		return dist;
	

	

		}
	

	

		int main(int argc, char const *argv[])
	

	

		{
	

	

		int vertexNum;
	

	

		while(cin>>vertexNum){
	

	

		int edgeNum;
	

	

		cin>>edgeNum;
	

	

		//初始化
	

	

		for(int i=0;i<vertexNum;++i){
	

	

		root[i]=i;
	

	

		for(int j=0;j<vertexNum;++j){
	

	

		distances[i][j]=-1;
	

	

		}
	

	

		distances[i][i]=0;
	

	

		}
	

	

		for(int k=0;k<edgeNum;++k){
	

	

		int edgePointA,edgePointB;
	

	

		cin>>edgePointA>>edgePointB;
	

	

		int rootOfPointA=findRootOf(edgePointA);
	

	

		int rootOfPointB=findRootOf(edgePointB);
	

	

		//如果AB已经在同一个集合里了
	

	

		//那么这条边的长度一定比当前AB距离的长度要长
	

	

		//故舍去,跳过此次松弛操作
	

	

		if(rootOfPointA==rootOfPointB)continue;
	

	

		int edgeDist=getEdgeDist(k);//计算当前这条边的长度;
	

	

		for(int i=0;i<vertexNum;++i){
	

	

		//i与A不在一个集合里?抱歉我们无法进行这次距离的更新
	

	

		if(rootOfPointA!=findRootOf(i))continue;
	

	

		for(int j=0;j<vertexNum;++j){
	

	

		//j与B不在一个集合里?抱歉我们也无法进行这次距离的更新
	

	

		if(rootOfPointB!=findRootOf(j))continue;
	

	

		distances[j][i]=distances[i][j]=
	

	

		(distances[i][edgePointA]+distances[edgePointB][j]+edgeDist)%100000;
	

	

		}
	

	

		}
	

	

		//A B原来不在同一个集合里,现在我们把它们连接起来
	

	

		root[rootOfPointB]=rootOfPointA;
	

	

		
	

	

		}
	

	

		for(int i=1;i<vertexNum;++i)cout<<distances[0][i]<<endl;
	

	

		}
	

	

		return 0;
	

	

		}
	

/*综合一下，有两种方法，第一种就是使用大整数+Dijkstra，第二种就是上面大神*/
/*提到的使用并查集的方法，如果两个点不属于一个集合，则合并这两个点*/
/*方法一：使用Dijkstra算法，只不过要用到与大数有关的计算*/
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAXN 100
using namespace std;

struct Edge{
    int to;                                    /*边的一个顶点*/
    string length;                             /*边长*/
    Edge(int t, string l): to(t), length(l) {}
};

struct Point{
    int number;                                /*点编号*/
    string distance;                    /*距离源点距离*/
    Point(int n, string d): number(n), distance(d) {}
    bool operator<(const Point &p) const{
        return distance>p.distance;          /*因为下面用到优先级队列，优先级队列默认是大根堆，而我们要用的是小根堆，所以注意这里return是大于号*/
    }
};

vector<Edge> graph[MAXN];                   /*使用邻接表存储图*/
string dis[MAXN];                       /*距离源点的距离*/

string adds(string s1, string s2){             /*字符串加法*/
    int carry=0, current;
    int i=s1.size()-1;
    int j=s2.size()-1;
    string ans;
    while(i>-1 && j>-1){
        current=s1[i]-'0'+s2[j]-'0'+carry;
        carry=current/10;
        ans+=current%10+'0';
        i--;
        j--;
    }
    while(i>-1){
        current=s1[i]-'0'+carry;
        carry=current/10;
        ans+=current%10 + '0';
        i--;
    }

    while(j>-1){
        current=s2[j]-'0'+carry;
        carry=current/10;
        ans+=current%10+'0';
        j--;
    }
    if(carry)                /*加法还有进位要再加1*/
        ans+="1";
    reverse(ans.begin(),ans.end());     /*因为ans正好与正确结果相反，所以使用reverse函数对字符串进行求逆，头文件是algorithm*/
    return ans;
}

string multiple(string s,int k){       /*字符串乘法*/
    int carry=0;
    for(int i=s.size()-1;i>-1;i--){
        int current=(s[i]-'0')*k+carry;
        s[i]=current%10+'0';
        carry=current/10;
    }
    if(carry)
        s=to_string(carry)+s;
    return s;
}

int Divide(string s){              /*字符串除法用于求模*/
    int remainder=0;
    for(int i=0;i<s.size();i++){
        int current=10*remainder+s[i]-'0';
        remainder=current%100000;
        s[i]=current/100000;
    }
    return remainder;
}

bool cmpString(string s1,string s2){     /*两个字符串数比较大小*/
    if(s1.size()>s2.size()) return true;  /*位数多则一定大*/
    else if(s1.size()<s2.size()) return false;
    else{
        for(int i=0;i<s1.size();i++){
            if(s1[i]-'0'>s2[i]-'0')
                return true;
            else if(s1[i]-'0'<s2[i]-'0')
                return false;
        }
    }
    return false;               /*两个数相等*/
}

void Dijkstra(){
    dis[0]="0";
    priority_queue<Point> Q;         /*使用优先级队列，方便找出距离源点最近的点*/
    Q.push(Point(0,dis[0]));
    while(!Q.empty()){
        int u=Q.top().number;
        Q.pop();
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].to;
            string d=graph[u][i].length;
            string l=adds(dis[u],d);
            if(cmpString(dis[v],l)){
                dis[v]=l;
                Q.push(Point(v,dis[v]));
            }
        }
    }
    return ;
}

int main(){
    int n, m, a, b;
    string INF="1";
    for(int i=0;i<1000;i++){   /*尽可能求一个大点的数用于路径长度的初始化*/
        INF=multiple(INF,2);
    }

    while(cin>>n>>m){
        string l="1";
        memset(graph,0,sizeof(graph));     /*初始化*/
        fill(dis,dis+n,INF);
        for(int i=0;i<m;i++){
            cin>>a>>b;
            graph[a].push_back(Edge(b,l));
            graph[b].push_back(Edge(a,l));
            l=multiple(l,2);
        }
        Dijkstra();
        for(int i=1;i<n;i++){
            if(dis[i]==INF)
                cout<<-1<<endl;
            else
                cout<<Divide(dis[i])<<endl;
        }
    }
    return 0;
}
------------------------------------------------------------------------
/*方法二，使用并查集，因为后面边的长度比前面所有边长之和还要长*/
/*所以后面加的边就不用再考虑，如果两个点不属于一个集合，*/
/*直接合并这两个点即可，此时长度一定是最短的*/

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<climits>
#define INF INT_MAX
#define N 101
using namespace std;

struct Point{
    int number;
    int distance;
    Point(int n, int d): number(n), distance(d) {}
    bool operator<(const Point &p) const{
        return distance>p.distance;
    }
};

struct Edge{
    int to;
    int length;
    Edge(int t, int l): to(t), length(l) {}
};

int dis[N];
vector<Edge> graph[N];
int father[N];
int height[N];

void Init(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
    }
    return ;
}

int Find(int x){
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y])
            father[x]=y;
        else if(height[x]>height[y])
            father[y]=x;
        else{
            father[y]=x;
            height[x]++;
        }
    }
    return ;
}

void Dijkstra(){
    dis[0]=0;
    priority_queue<Point> Q;
    Q.push(Point(0,dis[0]));
    while(!Q.empty()){
        int u=Q.top().number;
        Q.pop();
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].to;
            int d=graph[u][i].length;
            if(d+dis[u]<dis[v]){
                dis[v]=d+dis[u];
                Q.push(Point(v,dis[v]));
            }
        }
    }
    return ;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        Init(n);
        memset(graph,0,sizeof(graph));
        fill(dis,dis+n,INF);
        int len=1;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            if(Find(a)!=Find(b)){             /*两个点不属于一个集合*/
                Union(a,b);
                graph[a].push_back(Edge(b,len));
                graph[b].push_back(Edge(a,len));
            }
            len=(len*2)%100000;
        }
        Dijkstra();
        for(int i=1;i<n;i++){
            if(dis[i]==INF)
                cout<<-1<<endl;
            else
                cout<<dis[i] % 100000<<endl;
        }
    }
    return 0;
}

	

	// 这道题有点变态，常规做法可以考虑构建大整数结构体，结合最短路径问题
// 由于题目中路径长度有特殊性质，后来的第k条道路比前面k-1条距离之和还要小
// 如果节点a和b在之前已经被联通，那么后来的可联通ab的道路肯定不是最短距离
// 所以，当a、b未联通，出现可以联通a与b的道路时：
// 1. 首先联通a与b，更新dist[a][b]
// 2. 同时更新a所在的连通域的节点与b所在连通域节点之间的组合: dist[x][y] = dist[x][a] + dist[a][b] + dist[b][y]  
// （由于x是a所在连通域内的节点，包括a自身，x与a必定已经联通，dist不为-1；y也同理
// 更新时的距离计算只要乘幂取模就行，可以忽略取模之后对幂运算大小的改变，此时大小已无关重要)
// 3. 将a与b合并



	#include <iostream>
using namespace std;



	int dist[105][105]={};
int parent[105] = {};



	int find(int x){
    if (parent[x] == -1)
        return x;
    else{
        int temp = find(parent[x]);
        parent[x] = temp;
        return temp;
    }
}



	int get_mod(int base, int times){
    int ans = 1;
    for (int i=0; i<times; i++){
        ans *= base;
        ans %= 100000;
    }
    return ans;
}



	int main(){
    int n,m;
    cin >> n >> m;
    
    for (int i=0; i<n; i++)
        parent[i] = -1;
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++)
            dist[i][j] = -1;
        dist[i][i] = 0;
    }
    
    for (int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        int pa = find(a);
        int pb = find(b);
        if (pa != pb){
            int d = get_mod(2, i);
            // 核心部分：对a所在连通域和b所在连通域中所有的节点组合，都更新距离（此时必定是最小距离）
            for (int j=0; j<n; j++){
                if (find(j) == pa){
                    for (int k=0; k<n; k++){
                        if (find(k) == pb){
                            dist[j][k] = dist[k][j] = (dist[j][a]+ d + dist[b][k])%100000;
                        }
                    }
                }
            }
            parent[pb] = pa;
        }
    }
    
    for (int i=1; i<n; i++)
        cout << dist[0][i] << endl;
}

#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 101;
const int INF = INT_MAX;    //无穷设为很大的数

struct Edge {
    int to;     //终点
    int length; //长度
    Edge(int to, int length): to(to), length(length) {}
};

struct Point {
    int number;     //点的编号
    int distance;   //源点到该点距离
    Point(int number, int distance): number(number), distance(distance) {}
    bool operator<(const Point& p)const {
        return distance > p.distance;       //距离小的优先级高
    }
};

vector<vector<Edge>>graph(MAXN);    //邻接表实现的图
vector<int>dis(MAXN);               //源点到各点距离
//并查集数据结构
vector<int>father(MAXN);            //父亲结点
vector<int>height(MAXN);            //结点高度

//并查集操作
void Initial(int n) {               //初始化并查集
    for (int i = 0; i < n; i++) {
        father[i] = i;              //每个结点的父亲为自己
        height[i] = 0;              //每个结点的高度为0
    }
}

int Find(int x) {                       //查找根结点
    if (x != father[x]) {               //路径压缩
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {  //合并集合
    x = Find(x);
    y = Find(y);
    if (x != y) {   //矮树作为高树的子树
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

//迪杰斯特拉算法求单源最短路径，s为源点
void Dijkstra(int s) {
    priority_queue<Point>myPriorityQueue;
    dis[s] = 0;
    myPriorityQueue.push(Point(s, dis[s]));
    while (!myPriorityQueue.empty()) {
        int u = myPriorityQueue.top().number;   //离源点最近的点
        myPriorityQueue.pop();
        for (const auto& i : graph[u]) {
            int v = i.to;
            int d = i.length;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                myPriorityQueue.push(Point(v, dis[v]));
            }
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        fill(dis.begin(), dis.begin() + n, INF);    //距离初始化为无穷
        Initial(n); //初始化并查集
        for (int k = 0, length = 1; k < m; k++, length *= 2, length %= 100000) {
            int from, to;       //道路的起点和终点
            cin >> from >> to;
            //由于第K条道路的长度为2^K，一定大于前K条道路长度之和
            //因此，若第K条道路连接的两点已有路径，则第K条道路一定不会在最短路径中
            //这种情况下，可将第K条道路忽略，否则再将其作为边加入图的邻接表中
            if (Find(from) != Find(to)) {   //判断两点是否连通（已有路径）
                Union(from, to);
                graph[from].push_back(Edge(to, length));
                graph[to].push_back(Edge(from, length));
            }
        }
        Dijkstra(0);
        for (int i = 1; i < n; i++) {
            cout << (dis[i] == INF ? -1 : dis[i] % 100000) << endl;
        }
    }
    return 0;
}