原题传送门

题意

有  个点的图，任意一点  到可去另外一点  必须互质，即   。

图无边权，但是拥有点权。求到终点  的最短距离。

思路

此题需使用  算法求最短路。最后要求  到  的最短路径，如果直接暴力算最短路，肯定   ，怎么办呢？

考虑每次压入优先队列时，带上当前体力值，这样，就可以记录上次的最短距离。

性质

•  算法的运算特征：由当前最小值向连着的点拓展。
• 此图的特性：没有边权，只有从一点到走廊（边）上才会耗费体力值。

由此即可得：当第一次对终点  进行松弛操作时的值就是答案。

因为对于边有权值的图 在我们用点  对终点  松弛之后 另外的一个点  对  进行松弛的结果可能更小.

code

#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;
}