自己一开始写了个，才60分，效率不高，后来看了题解。
参考题解：https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<iostream> #include<cstring> #include<queue> #define MAXN 1000000 #define MAXM 2000000 #define MOD 100003 using namespace std; int n,m; int v[MAXM+5],nxt[MAXM+5]; bool visited[MAXM+5]; int fst[MAXN+5]; int dis[MAXN+5]; int cnter[MAXN+5]; int edgePtr=0; void edgePush(int s,int e){ edgePtr++; nxt[edgePtr]=fst[s]; v[edgePtr]=e; fst[s]=edgePtr; } void SP(){ memset(visited,false,sizeof(visited)); memset(dis,0x7f,sizeof(dis)); queue<int> q,qd; q.push(1);qd.push(0); while(!q.empty()){ int node=q.front(),dist=qd.front(); q.pop();qd.pop(); if(visited[node])continue; visited[node]=true; dis[node]=dist; for(int e=fst[node];e!=-1;e=nxt[e]){ if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){ dis[v[e]]=dis[node]+1; q.push(v[e]);qd.push(dis[v[e]]); } } } } void DFS(int node,int dist){ if(dist!=dis[node])return; cnter[node]++; cnter[node]%=MOD; for(int e=fst[node];e!=-1;e=nxt[e]){ if(visited[e])continue; visited[e]=true; DFS(v[e],dist+1); visited[e]=false; } } int main(){ memset(fst,-1,sizeof(fst)); ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; if(x==y)continue; edgePush(x,y); edgePush(y,x); } SP(); memset(visited,false,sizeof(visited)); DFS(1,0); for(int i=1;i<=n;i++)cout<<cnter[i]<<endl; } |
100分的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<iostream> #include<cstring> #include<queue> #define MAXN 1000000 #define MAXM 2000000 #define MOD 100003 using namespace std; int n,m; int v[MAXM+5],nxt[MAXM+5]; bool visited[MAXM+5]; int fst[MAXN+5]; int dis[MAXN+5]; int cnter[MAXN+5]; int edgePtr=0; void edgePush(int s,int e){ edgePtr++; nxt[edgePtr]=fst[s]; v[edgePtr]=e; fst[s]=edgePtr; } void SP(){ memset(visited,false,sizeof(visited)); memset(dis,0x7f,sizeof(dis)); queue<int> q,qd; q.push(1);qd.push(0); cnter[1]=1; while(!q.empty()){ int node=q.front(),dist=qd.front(); q.pop();qd.pop(); if(visited[node])continue; visited[node]=true; dis[node]=dist; for(int e=fst[node];e!=-1;e=nxt[e]){ if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){ dis[v[e]]=dis[node]+1; q.push(v[e]);qd.push(dis[v[e]]); cnter[v[e]]+=cnter[node]; cnter[v[e]]%=MOD; }else if(dis[v[e]]==dis[node]+1){ cnter[v[e]]+=cnter[node]; cnter[v[e]]%=MOD; } } } } int main(){ memset(fst,-1,sizeof(fst)); ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; if(x==y)continue; edgePush(x,y); edgePush(y,x); } SP(); for(int i=1;i<=n;i++)cout<<cnter[i]<<endl; } |