求救求救
查看原帖
求救求救
909162
Dream_of_Glory楼主2023/8/18 10:18

为啥只能过一个点呀

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;
const int mod=100003;

#define PII pair<int,int>
#define xx first
#define yy second

int d[N];
bool b[N];
int ans[N];
vector<int> a[N];

struct cmp1
{
	bool operator() (const PII a,const PII b)
	{
		return a.xx>b.xx;
	}
};

void dijkstra(int x)
{
	priority_queue<PII,vector<PII>,cmp1>q;

	d[x]=0; ans[x]=1;
	q.push({1,x});

	while(!q.empty())
	{
		auto t=q.top();
		q.pop();

		if(b[t.yy]) continue;
		b[t.yy]=1;

		for(int i=0;i<a[t.yy].size();i++)
		{
			int ne=a[t.yy][i];

			if(!b[ne])
			{
				if(d[ne]==d[t.yy]+1)
				{
					ans[ne]+=ans[t.yy];
					ans[ne]%=mod;
				}
				
				else if(d[ne]>d[t.yy]+1)
				{
					ans[ne]=ans[t.yy];
					d[ne]=d[t.yy]+1;
					q.push({ans[ne],ne});
				}
			}
		}
	}
}

int main()
{
	memset(d,0x3f3f3f3f,sizeof(d));

	int n,m; cin>>n>>m;

	for(int i=1;i<=m;i++)
	{
		int x,y; cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}

	dijkstra(1);

	for(int i=1;i<=n;i++)
	cout<<ans[i]<<"\n";

}
2023/8/18 10:18
加载中...