Codeforces Round #843 (Div. 2) D. Friendly Spiders

题目：

• $n（n<=3e5）$ 个节点，
• 每个节点 $a_i$ $<=$ $3e5$ ，
• 若 $gcd（a_i,a_j）$ $!=$ $1$，则 $i$ 和 $j$ 存在一条边，
• 求 $s$ 到 $t$ 的最短路径，输出该路径

解析：

• 我们给每个数的质因数找个中转点，这样建图的边数从 $n^2$ ，降到 $nlogn$ ，直接跑一个最短路，然后输出路径即可。

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];vector<int> g[300001+n];for(int i=1;i<=n;i++){int x=a[i];for(int j=2;j<=x/j;j++)if(x%j==0){while(x%j==0) x/=j;g[i].push_back(n+j);g[n+j].push_back(i);}if(x>1){g[i].push_back(n+x);g[n+x].push_back(i);}}vector<int> d(300001+n,0x3f3f3f3f),p(300001+n),st(300001+n);queue<int> Q;int s,t;cin>>s>>t;d[s]=0;Q.push(s);while(!Q.empty()){int u=Q.front();Q.pop();if(st[u]) continue;for(auto j:g[u])if(d[j]>d[u]+1){d[j]=d[u]+1;p[j]=u;Q.push(j);}}if(d[t]==0x3f3f3f3f) cout<<"-1"<<endl;else{vector<int> ans;int x=t;while(x){if(x<=n) ans.push_back(x);x=p[x];}reverse(ans.begin(),ans.end());cout<<ans.size()<<endl;for(auto ai:ans)cout<<ai<<" ";cout<<endl;}return 0;
}