小V画了一幅图。
这图真好看！
这图真好看！
这图真好看！
对于一个无向图，重新定义相连的两点u,v：存在至少一条路径上所有边边权的最大公因数!=1的连接u,v的路径；两点间最短路径为连接两点的路径中所有边权和最小的一条。
球两点间的最短路径长度。
第一行两个数n,m，表示n个点(1~n)，m条边。
接下来m行，每行三个数u,v,w,表示在点u和点v间有一条边权为w的边
接下来1行，两个数s, t，询问s到t的最短路径的长度。
输出格式：输出一行，表示s到t的最短路径的长度，如果不存在，则输出-1。
n<=80,000, m<=500,000
w[i]<=100,000
所有数据为正整数
数据很随机
（虽然有点不随机，但是不卡算法（不卡已知算法）图绝对是随机的）
奇怪的算法被卡了出题者概不负责
先分别对起点和终点连出的边权进行质因数分解，从小到大枚举他们公共的因子，这样在求最短路的时候边权要是这个因子的倍数。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define f(i,l,r) for(i=(l);i<=(r);i++) #define fe(i,u) for(i=head[(u)];~i;i=e[i].next) using namespace std; const int MAXM=1000005,MAXN=80005; struct Edge{ int v,w,next; }e[MAXM]; struct Node{ int d,id; bool operator < (const Node& x)const{ return d>x.d; } }; priority_queue<Node> q; int n,m,s,t,ans=1000000000; int head[MAXN],tot; int prime[10000],inp[100005],prime_num; int used[2][10000]; int dis[MAXN],vis[MAXN]; int heap[2][MAXN],sz; inline void add(int u,int v,int w) { e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot++; } inline void pushup(int p) { int fa=p>>1,a=heap[0][p],id=heap[1][p]; while(fa&&a<heap[0][fa]){ heap[0][p]=heap[0][fa]; heap[1][p]=heap[1][fa]; p=fa; fa>>=1; } heap[0][p]=a; heap[1][p]=id; } inline void pushdown(int p) { int son=p<<1,a=heap[0][p],id=heap[1][p]; while(son<=sz){ if(son<sz&&heap[0][son]>heap[0][son+1]){ son++; } if(heap[0][son]>=a) break; heap[0][p]=heap[0][son]; heap[1][p]=heap[1][son]; p=son; son<<=1; } heap[0][p]=a; heap[1][p]=id; } inline void insert(int a,int id) { heap[0][++sz]=a; heap[1][sz]=id; pushup(sz); } inline void Pop() { heap[0][1]=heap[0][sz]; heap[1][1]=heap[1][sz--]; if(sz) pushdown(1); } inline void Maketable() { int i,j; for(i=2;i<=100000;i++){ if(!inp[i]){ prime[prime_num++]=i; } for(j=0;j<prime_num&&i*prime[j]<=100000;j++){ inp[i*prime[j]]=1; if(i%prime[j]==0) break; } } return; } inline void Dijkstra(int x) { int i; memset(dis,60,sizeof(dis)); memset(vis,0,sizeof(vis)); sz=0; dis[s]=0; insert(dis[s],s); while(sz){ int u=heap[1][1],d=heap[0][1]; Pop(); if(vis[u]) continue; vis[u]=1; fe(i,u){ int w=e[i].w,v=e[i].v; if(w%x) continue; if(dis[v]>d+w){ dis[v]=d+w; insert(dis[v],v); } } } ans=min(ans,dis[t]); } int main() { memset(head,-1,sizeof(head)); Maketable(); int i,u,v,w; scanf("%d%d",&n,&m); f(i,1,m){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d%d",&s,&t); fe(i,s){ w=e[i].w; int num=0; while(w!=1){ while(w%prime[num]) num++; used[0][num]=1; while(w%prime[num]==0) w/=prime[num]; } } fe(i,t){ w=e[i].w; int num=0; while(w!=1){ while(w%prime[num]) num++; used[1][num]=1; while(w%prime[num]==0) w/=prime[num]; } } f(i,0,prime_num-1){ if(used[0][i]&&used[1][i]){ Dijkstra(prime[i]); } } if(ans>1000000){ printf("-1\n"); } else{ printf("%d\n",ans); } return 0; }