#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,u,v,dis[1005][1005];
vector<int> a[1005];
queue<int> q;
bool vis[1005];
void spfa(int x){
q.push(x);
memset(vis,false,sizeof(vis));
vis[x]=true;
dis[x][x]=0;
while(!q.empty()){
int t=q.front();
q.pop();
vis[t]=false;
for(int i=0;i<a[t].size();i++){
if(dis[x][a[t][i]]>dis[x][t]+1){
dis[x][a[t][i]]=dis[x][t]+1;
if(!vis[a[t][i]]){
q.push(a[t][i]);
vis[a[t][i]]=true;
}
}
}
}
return;
}
int qpow(int a,int b){
int sum=1;
while(b){
if(b&1) sum=sum*a%mod;
a=a*a%mod;
b>>=1;
}
return sum;
}
int main(){
freopen("polaris.in","r",stdin);
freopen("polaris.out","w",stdout);
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
for(int i=1;i<=n;i++){
spfa(i);
sort(dis[i]+1,dis[i]+n+1);
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans=(ans+qpow(2,n-j)*dis[i][j])%mod;
}
}
printf("%d",ans);
return 0;
}
体重没有说要qpow啊
还有为啥要spfa，边权为1，BFS不行吗。
这题的难度也没有提高组吧
额，老师说这道题大概是提高组第二题，放在第三题是对第三题的侮辱（
为什么不能 spfa？不是一样的么
spfa复杂度高.
BFS复杂度 O(n) spfa 复杂度 O(nm)
可我是WA呀
不用qpow，题目中没说
e那我就不知道了，你问金杭东巨佬吧
提高第二题？
这就提高第一题水平吧
嗯嗯差不多，所以不用快速幂？这是求答案的呀，不然怎么算
不是这哪来的qpow
哦，看错要求的东西了，我再看看题目
你没开long long啊
不是 %mod 吗？
这题的确有的确有提高第二题水平
这你见过%1e9不用开longlong 的吗
建议开long long
哦哦，好的
快速幂不是a*a吗，这不爆int了