东华大学2020年程序设计竞赛（同步赛）C.City Supplies

题目链接

题目描述

YZ is the king of the kingdom. There are n cities in his kingdom. To celebrate the 50th anniversary of the founding of his country, YZ decided to distribute supplies as a reward to all the cities.
We all know that the further the city is from the capital (always at 1), the more it will cost to transport. We define K as the shortest distance between a city and the capital, and ignore the difference in distance between different cities(all is 1 unit). Cost from capital to the city is
$2^K$

2K .
Now YZ gives you the map of his kingdom, and asks you if you can calculate the total cost.
(We guarantee that it is a connected graph.)

输入描述:

The first line contains two integers n and m
$(1 le n le 10^6,n-1 le m le min(2*10^6,(n-1)*n/2))$

(1≤n≤106,n−1≤m≤min(2∗106,(n−1)∗n/2)), which means there are n cities and m roads.
The next m lines contains two integers u and v, denoting there is a road connecting city u and city v.

输出描述:

Print the only line containing a single integer. It should be equal to the total cost mod 1e9+7.

示例1

输入

3 2 1 2 2 3 

输出

6 

示例2

输入

7 6 1 2 1 3 1 4 3 5 3 6 4 7 

输出

18 

这题不难，用 BFS 求出 1 到每个点的距离，然后跑一遍 O(N) 计算答案即可，数据量大要用快读，AC代码如下:

#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=1e6+5; const ll mod=1e9+7; vector<int>g[N]; ll d[N]={0},vis[N]={0}; ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;} void bfs(int u){     queue<int>q;     q.push(u); while(!q.empty()){ int a=q.front();         q.pop(); for(int b:g[a]){ if(!vis[b]) {                 d[b]=d[a]+1;                 vis[b]=1;                 q.push(b); } } } } inline int read() { int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int main(){ int n,m,x,y;      n=read();      m=read(); while(m--){         x=read(),y=read();         g[x].push_back(y);         g[y].push_back(x); } bfs(1);      ll ans=0; for(int i=2;i<=n;i++) ans=(ans+power(2,d[i]))%mod;      cout<<ans; }