HHUOJ 1733 Shortest Path 2

Title Description
N cities, marked from 0 to N-1, M roads, the length of K road (K from 0) is 2^K, find the shortest distance from the city numbered 0 to other cities.

## input

In the first row, two positive integers N (2 <=N <=100) M (M <=500) denote N cities and M roads.
Next, line M has two integers, representing the numbers of the two cities that are connected.

## output

Line N-1 shows the shortest path from No. 0 city to other cities. If it cannot reach, output-1. The value is too large to output as the result of MOD 100000.

## sample input

4 3
0 1
1 2
2 0

## sample output

1
3
-1

Because m < 500, it is necessary to use fast power modulus because:

2n&gt;∑i=1n−12i2^n&gt;\sum_{i=1}^{n-1} 2^i 2n>i=1∑n−1​2i
So we can use one and look up. When the parents of the two input nodes are the same, we don't need to record the path any more. Otherwise, the answer is wrong. The AC code is as follows:

#include<bits/stdc++.h>
#define maxn 105
#define inf 1e9
using namespace std;
typedef long long ll;

ll a[maxn][maxn];
ll d[maxn],vis[maxn];
ll father[maxn];
ll n,m;

ll findfather(int i)
{
while(i!=father[i])
{
i=father[i];
}
return i;
}

ll poww(ll a,ll b)
{
ll ans=1,base=a;
while(b)
{
if(b&1) ans=ans*base%100000;
base=base*base%100000;
b>>=1;
}
return ans;
}

void dijkstra(ll s)
{
fill(d,d+maxn,inf);
d[s]=0;
for(ll i=0;i<n;i++){
ll u=-1,minn=inf;
for(ll j=0;j<n;j++){
if(vis[j]==0 && d[j]<minn)
{
u=j;
minn=d[j];
}
}
if(u==-1) return ;
vis[u]=1;
for(ll v=0;v<n;v++)
{
if (d[u]+a[u][v]<d[v] && vis[v]==0)
{
d[v]=d[u]+a[u][v];
}
}
}
}

int main()
{
while(cin>>n>>m){
ll x,y,k;
fill(a[0],a[0]+maxn*maxn,inf);
memset(d,0,sizeof(0));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
father[i]=i;
}
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
ll m=findfather(x);
ll n=findfather(y);
if(m!=n) father[m]=n;
else continue;
a[x][y]=poww(2,i);
a[y][x]=poww(2,i);
}
dijkstra(0);
for(int i=1;i<n;i++)
{
if(d[i]!=inf)printf("%d\n",d[i]%100000);
else printf("-1\n");
}
}
return 0;
}