这道题就是很水啊, 水到我居然不用最短路算法就做了出来. 因为每条边的权值都为 1, 最短路计数, 无异于遍历整张图, 记录有多少个结点可以到达这个点, 且路径长度为最小的那个. 用 BFS, 保证第一次访问到结点时的路径长度就是到起点的最短路, 后面只需要加个条件判断就行. 其实 SPFA,Dijkstra 堆优化也可以, 就是懒得去写, 他只需要求最短路并且统计最短路到每个结点的次数就可以了 (当然因为本题的边权都为 1). 另外他说有重边, 这个没关系, 还说有自环, 就吓到我了 (怎么可能), 所以加上一个当前弧优化 QwQ.
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<queue>
- using namespace std;
- inline int get_num() {
- int num;
- char c;
- while((c=getchar())=='\n'||c==''||c=='\r');
- num=c-'0';
- while(isdigit(c=getchar())) num=num*10+c-'0';
- return num;
- }
- void put_num(int i) {
- if(i>9) put_num(i/10);
- putchar(i%10+'0');
- }
- const int maxn=1e6+5,maxm=4e6+5,inf=0x3f3f3f3f;
- int n,m,head[maxn],eid,vis[maxn],d[maxn],cnt[maxn];
- struct edge {
- int v,next;
- } E[maxm];
- void insert(int u,int v) {
- E[eid].v=v;
- E[eid].next=head[u];
- head[u]=eid++;
- }
- queue<int> q;
- void bfs() {
- memset(d,inf,sizeof(d));
- d[1]=0;
- cnt[1]=1; // 看样例的意思, 1 的最短路条数开始就是 1
- q.push(1);
- while(!q.empty()) {
- int u=q.front();q.pop();
- if(vis[u]) continue;
- vis[u]=1;
- for(int& p=head[u];p+1;p=E[p].next) {
- int v=E[p].v; // 答案要求 mod 100003
- if(d[v]==d[u]+1) cnt[v]+=cnt[u],cnt[v]%=100003;
- if(d[v]==inf) d[v]=d[u]+1,cnt[v]+=cnt[u],cnt[v]%=100003;
- q.push(v);
- }
- }
- }
- int main() {
- n=get_num();m=get_num();
- memset(head,-1,sizeof(head));
- int u,v;
- for(int i=1;i<=m;++i) {
- u=get_num();v=get_num();
- insert(u,v);insert(v,u); // 无向图
- }
- bfs();
- for(int i=1;i<=n;++i) {
- if(i!=1) putchar('\n');
- printf("%d",cnt[i]);
- }
- return 0;
- }
AC 代码
来源: http://www.bubuko.com/infodetail-2747516.html