求助!!Codeforces 第12个点re
查看原帖
求助!!Codeforces 第12个点re
581722
HarryZ楼主2023/6/18 10:25

代码奉上,请各位dalao帮个忙

#include <bits/stdc++.h>
using namespace std;
struct point {
	int dis,k;
};
struct cmp {
	bool operator()(point x,point y) {
		return x.dis>y.dis;
	}
};
priority_queue<point,vector<point>,cmp>q;
int head[600010],e[600010],w[600010],dis[600010],cnt,nxt[600010],used[300010], a[300010], lst[300010];
int n,e2,s;
int ans[300010], o = 0;
void addEdge(int a,int b,int c) {
	cnt++;
	e[cnt]=b,w[cnt]=c,nxt[cnt]=head[a],head[a]=cnt;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}
	cin >> s >> e2;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j || __gcd(a[i], a[j]) == 1) continue;
			addEdge(i, j, 1), addEdge(j, i, 1);
		}
	}
	memset(dis,0x7f,sizeof(dis));
	dis[s]=1;
	q.push(point {0,s});
	while(!q.empty()) {
		point u=q.top();
		q.pop();
		int x=u.k,y=u.dis;
		if(used[x]==1) continue;
		used[x]=1;
		for(int i=head[x]; i; i=nxt[i]) {
			int v=e[i],va=w[i];
			if(dis[v]>dis[x]+va) {
				dis[v]=dis[x]+va;
				if(used[v]==0) q.push(point {dis[v],v}), lst[v] = u.k;
			}
		}
	}
	if(dis[e2]==0x7f7f7f7f) cout<<"-1 ";
	else {
		cout << dis[e2] << endl;
		for (int i = e2; i; i = lst[i]) ans[++o] = i;  
		for (int i = o; i >= 1; i--) cout << ans[i] << ' ';
	}
	return 0;
}
2023/6/18 10:25
加载中...