题目描述
N个城市,标号从0到N-1,M条道路,第K条道路(K从0开始)的长度为2^K,求编号为0的城市到其他城市的最短距离
输入描述
第一行两个正整数N(2<=N<=100)M(M<=500),表示有N个城市,M条道路
接下来M行两个整数,表示相连的两个城市的编号
输出描述
N-1行,表示0号城市到其他城市的最短路,如果无法到达,输出-1,数值太大的以MOD 100000 的结果输出。
输入样例
4 4
1 2
2 3
1 3
0 1
输出样例
8
9
11
分析
本题要求我们求出点0到其他所有点的最短路。
因为第k条边都要比k-1条边大2倍,所以第k条边大于第1条边到第k-1条边之和。
所以我们得出:
- 在添加第k条路径时,如果路径k连接的两个城市A 、B已经通过其他路径间接的连通了,那么第k条路径绝对不是AB间的最短路径(第k条路径之后的路径也不可能有比当前AB路径更短的路径了,因为第k条路径的长度会大于前k-1条路径的总和)
- 在添加第k条路径时,如果路径k连接的两个城市A 、B是第一次被连通了(也就是说此前没有任何路径能连通AB,包括通过多条路径间接连通),那么路径k就是AB之间的最短距离了,因为以后不可能存在更短的路径连接AB,以后的单条路径只会越来越长。
对于每一条边的信息:
- 如果这条边连接的城市a、b,已经在同一个集合里了(即已经联通了),那么当前的路径一定不是ab之间的最短路径了,忽略,继续看下一条路径。
- 如果这条路径连接的城市a、b不在同一个集合里(之前没有联通过),很好,这条路径是ab之间的最短路径。另外我们还可以看看通过这条路径能不能让a集合里的城市到b集合里的城市之间的路径更短呢?即是不是d[i][j]>(g[a][j]+g[b][k]+d) ?(注意i和a一个集合,j和b一个集合),如果是的话可以更新一下这个值。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 100000,N = 110;
int g[N][N],fa[N];
int n,m;
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int calc(int x) //计算路径长
{
int res=1;
while(x)
{
res=(res*2)%mod;
x--;
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
fa[i]=i;
for(int j=0;j<n;j++)
{
g[i][j]=-1; //两点之间互不可达
}
g[i][i]=0; //自己到自己的距离为0
}
int a,b;
for(int i=0;i<m;i++)
{
cin>>a>>b;
int faa=find(a),fbb=find(b);
if(faa==fbb) continue; //a,b在一个集合里,已经存在最短路了
int d=calc(i);
for(int j=0;j<n;j++)
{
if(find(j)==faa) //当前点在a的集合里
{
for(int k=0;k<n;k++)
{
if(find(k)==fbb) //当前点在b的集合里
{
g[j][k]=g[k][j]=(g[a][j]+g[b][k]+d)%mod; //更新j,k两点间的距离
}
}
}
}
fa[faa]=fbb; //合并a,b所在集合
}
for(int i=1;i<n;i++) cout<<g[0][i]<<endl;
return 0;
}