D. Lunar New Year and a Wander bfs+优先队列

题意

给出一个图，从1点开始走，每个点至少要经过一次（可以很多次），每次经过一个没有走过的点就把他加到走过点序列中，问最小字典序的序列是多少

思路

起始就是从每次可达的点的选取最小的那个走，拓展可达的点，然后重复直到走完了全部为止，直接用个bfs+优先队列即可

#include<bits/stdc++.h>

#include<stdlib.h>

using namespace std;

const int maxn = 3e5+5;

typedef long long ll;

#define F first

#define S second

#define pb push_back

#define pii pair<int ,int >

int a[maxn],c[maxn];

vector<int>G[maxn];

int vis[maxn];

bool cmp(int x,int y){

	char num1[10],num2[10];

	sprintf(num1,"%d",x);

	sprintf(num2,"%d",y);

	int len1=strlen(num1),len2=strlen(num2);

	for(int i=0;i<min(len1,len2);i++){

		if(num1[i]>num2[i]){

				return 0;

		}

		else if(num1[i]<num2[i])return 1;

	}

	return len1<=len2;

}

priority_queue<int,vector<int>,greater<int> >q;

void bfs(){

	q.push(1);

	vis[1]=1;

	while(!q.empty()){

		int tmp=q.top();

		q.pop();

	cout<<tmp<<" ";

		for(int i=0;i<G[tmp].size();i++)

		{

			int y=G[tmp][i];

			if(!vis[y]){q.push(y);vis[y]=1;}

		}

	}

}

int main(){

	int n,m,t,d;

	scanf("%d%d",&n,&m);

	int x,y;

	for(int i=0;i<m;i++){

		scanf("%d%d",&x,&y);

		G[x].pb(y);

		G[y].pb(x);

	}

	bfs();

	return 0;

}

巴特西

D. Lunar New Year and a Wander bfs+优先队列

D. Lunar New Year and a Wander bfs+优先队列

题意

思路

最新文章

热门文章