社区讨论

求救 最后两个点为何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 条回复,欢迎继续交流。

正在加载回复...