質問C:最短パス

題目はN個の都市を説明して、符号は0からN-1まで、M条の道路、第K条の道路(Kは0から)の長さは2^Kで、番号が0の都市がその他の都市までの最短距離を求めます.
1行目の2つの正の整数N(2<=N<=100)M(M<=500)を入力し、N都市、M道路、次にM行の2つの整数を入力し、接続された2都市の番号を表します.
出力N-1行は、0番都市から他の都市への最短ルートを示し、到達できなければ、出力-1、数値が大きすぎてMOD 100000の結果で出力します.
サンプル入力Copy 4 3 0 1 1 2 0サンプル出力Copy 1 3-1
最初は2^Kが大きいかもしれないと考えていなかったので、ずっと間違っていました...タイトル中M(M<=500)なので、最大2^500という数が大きく、直接表示できないので、タイトル中の最後の一言で「数値が大きすぎてMOD 100000の結果で出力する」ということになりますので、2の何回を求めるときに余裕を取る必要がありますが、これも問題をもたらしています.残りを取ると元のデータではなく、大きさも正確ではありません.どのように最短の経路を求めますか.タイトルにはもう一つ重要な言葉があります.「K番目の道(Kは0から)の長さは2^K」なので、2つの点の間で、最初に現れた道はこの2つの点の間の最短経路に違いありません.(1+2^1+2^2+2^(k-1)=2^(k-1)-1<2^k前のすべての点が経路上の点であっても、それらを合わせても最後の経路の長さはないので)、前の点間が連通している限り、これらの経路は最短経路であり、後から現れる経路は直接スキップし、受信しない.やはりディジェストラアルゴリズムで最短経路を求めるが,2つの点が1つの集合,すなわち2つの点の間に経路があるかどうかを判断し,セットを調べる必要がある.

#include 
#include
using namespace std;
int g[101][101];
bool visit[101];
int father[101],d[101];
int n;
int INF=0x3fffffff;
int f(int k)
{
    int s=1;
    for(int i=1; i<=k; i++)
    {
        s=(s*2)%100000;
    }
    return s;
}
void dij(int s)
{
    int i,j;
    fill(visit,visit+101,false);
    fill(d,d+101,INF);
    for(i=0; i<n; i++)
    {
        d[i]=g[s][i];
    }
    d[s]=0;
    visit[s]=true;
    for(i=1; i<n; i++)
    {
        int Min=INF;
        int u=-1;
        for(j=0; j<n; j++)
        {
            if(visit[j]==false&&d[j]<Min)
            {
                Min=d[j];
                u=j;
            }
        }
        if(u==-1)return;
        visit[u]=true;
        for(j=0; j<n; j++)
        {
            if(visit[j]==false&&g[u][j]+d[u]<d[j])
                d[j]=d[u]+g[u][j];
        }
    }
}
int findFather(int x)
{
    while(x!=father[x])
        x=father[x];
    return x;
}
int main()
{
    int m,i,a,b;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(i=0; i<n; i++)father[i]=i;
        fill(g[0],g[0]+101*101,INF);
        for(i=0; i<m; i++)
        {
            scanf("%d %d",&a,&b);
            int fatherA=findFather(a);
            int fatherB=findFather(b);
            if(fatherA!=fatherB)
            {
                father[fatherA]=fatherB;
                g[a][b]=g[b][a]=f(i);
            }
            else continue;
        }
        dij(0);
        for(i=1; i<n; i++)
        {
            if(d[i]==INF)printf("-1
");
            else printf("%d
",d[i]%100000);
        }
    }
    return 0;
}