## 题意
有 $n$ 个点的图，任意一点 $x$ 到可去另外一点 $y$ 必须互质，即 $\gcd(x,y)=1$。
图无边权，但是拥有点权。求到终点 $en$ 的最短距离。
---
## 思路
此题需使用 Dijkstra 算法求最短路。最后要求 $x$ 到 $y$ 的最短路径，如果直接暴力算最短路，肯定 TLE，怎么办呢？
考虑每次压入优先队列时，带上当前体力值，这样，就可以记录上次的最短距离。
---
**性质**
- Dijkstra 算法的运算特征：由当前最小值向连着的点拓展。
- 此图的特性：没有边权，只有从一点到走廊（边）上才会耗费体力值。
由此即可得：**当第一次对终点 $y$ 进行松弛操作时的值就是答案**。
---
## code
```cpp
#include<bits/stdc++.h>
#define k pair <int, int>//宏定义
using namespace std;
const int N = 4.5e3+10;
static inline int read () {//快读
int x = 0；bool f = 1; char s = getchar();
while(s<'0'||s>'9'){if(s=='-')f=0;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^48);s=getchar();}
return f?x:-x;
}
//inline:内联函数
int T, n, a[N], h[N*N], cnt;//注意：一定是N*N!!!
struct edge {int to, next;} e[N*N];
static inline void add(int x,int y){//链式前向星存图
e[++cnt].to = y;
e[cnt].next = h[x];
h[x] = cnt;
}
bool vis[N];int dis[N];
priority_queue<k,vector<k>,greater<k> >q;//优先队列 pair型
static inline void dijkstra(int s, int en){//求最短路
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
priority_queue<k,vector<k>,greater<k> >().swap(q);//清零 且清空内存
dis[s] = 0;
q.push(make_pair(dis[s]+a[s], s));//first:最小值 second:编号
while(q.size()){
pair<int,int> u = q.top(); q.pop();
int x = u.first, y = u.second;
vis[y] = 1;
for(int i = h[y]; i; i = e[i].next) {
int v = e[i].to;
if (vis[v]) continue;//松弛处理
if (dis[v] > dis[y]+a[y]){//从点到边耗费体力
dis[v] = x;//上次的值
if (v == en){
printf("%d\n",dis[v]);
return ;
} q.push(make_pair(dis[v]+a[v], v));
}
}
} puts("-1\n");//到不了 输出 -1
return ;
}
signed main(void){
T=read();n=read();
for(int i = 2; i < n; ++ i)
for(int j = i+1; j <= n; ++ j)
if(__gcd(i, j) == 1){//判断互质 ，最大公因数为 1
add(i, j);
add(j, i);//无向图
}
while (T --) {
int x = read(), y = read();
for(int i = 1; i <= n; ++ i) a[i] = read();
dijkstra(x, y);//记得用快读，开 O2
}
return 0;
}
```