社区讨论
求救 最后两个点为何RE qwq
P1144最短路计数参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6lruuv
- 此快照首次捕获于
- 2025/11/20 06:57 4 个月前
- 此快照最后确认于
- 2025/11/20 06:57 4 个月前
CPP
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#define maxn 4000010
#define mode 100003
using namespace std;
struct node{
int to;
node* next;
}*con[maxn];
bool visit[maxn],tag[maxn];
int x,y,cnt[maxn],n,m,dl[maxn],head=1,tail=1,last=1,v;
node* p;
inline void addedge(int x,int y)
{
node* p;
p=new node;
p->to=y;
p->next=con[x];
con[x]=p;
}
inline void init()
{
for(int i=1;i<=n;++i)
con[i]=NULL;
memset(visit,0,sizeof(visit));
}
inline void bfs()
{
dl[tail]=1;visit[1]=true;
while(head<=tail)
{
v=dl[head];
p=new node;
p=con[v];
while(p!=NULL)
{
if(!visit[p->to])
dl[++tail]=p->to;
p=p->next;
}
if(last==head)
{
for(int i=last+1;i<=tail;++i)
{
(cnt[dl[i]]+=1)%=mode;
visit[dl[i]]=true;
}
last=tail;
}
head++;
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
if(x==y) continue;
addedge(x,y);
addedge(y,x);
}
bfs();
cnt[1]=1;
for(int i=1;i<=n;++i)
printf("%d\n",cnt[i]);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...