P1144的神奇玩意
  • 板块灌水区
  • 楼主Ptilopsis_
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/1/9 15:52
  • 上次更新2023/10/28 12:35:49
查看原帖
P1144的神奇玩意
524994
Ptilopsis_楼主2022/1/9 15:52

本蒟蒻要疯了

不越界但样例错误

#include<bits/stdc++.h>
#define maxn 1000002
#define mod 100003
using namespace std;
int n,m;
int dis[maxn],ans[maxn];
vector<int> a[maxn*2];
void bfs()
{
	for(int i=0;i<maxn;i++)
		dis[i]=-1;
	queue<int> q;
	dis[1]=0;
	ans[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<a[u].size();i++)
		{
			int v=a[u][i];
			
			if(dis[v]==-1)
			{
				dis[v]=dis[u]+1;
				q.push(v);
				ans[v]++;
			}
			if(dis[v]==dis[u]+1)
				ans[v]=(ans[v]+ans[u])%mod;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	bfs();
	return 0;
}

越界但样例正确

#include<bits/stdc++.h>
#define maxn 1000002
#define mod 100003
using namespace std;
int n,m;
int dis[maxn],ans[maxn];
vector<int> a[maxn*2];
void bfs()
{
	for(int i=0;i<maxn*2;i++)//此处越界
		dis[i]=-1;
	queue<int> q;
	dis[1]=0;
	ans[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<a[u].size();i++)
		{
			int v=a[u][i];
			
			if(dis[v]==-1)
			{
				dis[v]=dis[u]+1;
				q.push(v);
				ans[v]++;
			}
			if(dis[v]==dis[u]+1)
				ans[v]=(ans[v]+ans[u])%mod;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	bfs();
	return 0;
}

作战行动中发生了问题,请重启系统

2022/1/9 15:52
加载中...