$$\mathrm{魔术}$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{T}145393$ / $\mathrm{S}\mathrm{S}\mathrm{L}比赛1519$

题目

Marah 是一名魔法师，她生活的大陆上有 $n$ 座城市，城市之间通过 $m$ 条路径相连， 每条路径都以一个权值 。有一天，她突然想去 $n$ 号城市玩。

但是她很懒，于是她在路上行走的时候会用一点小小的法术，改变一下两座城之间的距离

但是她的法力也是很珍贵的，所以她决定，如果从她的家里出发，到达某个城市所经过的所有路径的权值的最大公约数为 $g$ ，从该城市出发前往下一个城市的路径的权值为 $w$ ，则经过这条路的时候会施法将这条路的路程缩 短为 $\frac{w}{gcd(g,w)}$ 。

现在 Marah 有 $Q$ 个家，她告诉了你这 $Q$ 个家在哪，并请你告诉她这 $Q$ 个家到 $n$ 号城市的最短距离。

输入

第一行两个数 $n,m$ ，表示有 $n$ 座城市， $m$ 条道路。

接下来 $m$ 行，每行三个数 $u,v,w$ ，表示 $u$ 号城市和 $v$ 号城市之间有一条权值为 $w$ 的路。

接下来一行一个数 $Q$ ，表示 Marah 有 $Q$ 个家。

接下来 $Q$ 行，其实第 $i$ 行有一个数 $p_i$ ，表示 H 的第 $i$ 个家在 $P_i$ 号城市。

输出

输出 $Q$ 行，第 $i$ 行输出一个数表示 Marah 的第 $i$ 个家到 $n$ 号城市的最短距离。

样例输入1

4 3
1 2 2
2 3 4
3 4 6
3
1
2
3

样例输出1

6
4
1

样例输入2

10 20
3 4 34
1 5 97
4 1 85
7 8 81
6 1 23
8 3 57
5 2 77
9 1 68
10 3 95
2 10 68
8 5 21
6 8 68
5 7 34
2 8 91
2 7 37
3 7 68
2 9 68
8 4 68
5 10 68
2 8 68
7
1
7
4
6
3
9
5

样例输出2

3
3
3
3
1
2
1

数据范围

对于 $20\%$ 的数据，有 $2\le n\le 10,1\le q\le 10,m\le 100$

对于 $50\%$ 的数据，有 $2\le n\le 100,1\le q\le 100,m\le 500$

对所有数据:

$2\le n\le 1000$

$n-1\le m\le 2000$ ，保证每个点均可到达 $n$

$1\le q\le 1e5$

$1\le max(w)\le 500$

思路

这道题是一道最短路，做法极其的秀。

我们看 $n$ 只有 $1000$ ，而且 $max(w)$ 最大才 $500$ ，直接反手把一个点拆成 $500$ 个！
（管你傻没傻，反正我是傻了）
然后就每个点拆出来的 $500$ 个点都分别表示到现在路径的 $gcd$ 是多少。
然后就恶心建图跑 spfa 。

（不会吧不会吧，不会真有人不知道怎么求其他点到同一个点的最短路吧）
（我一定不会告诉你可以反向建图然后从终点开始跑最短路的）

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node {
int x, to1, to2, nxt;
}e[10000001];
struct node1 {
int now, gcd;
};
int n, m, x, y, z, KK, qu;
int le[1001][501], dis[1001][501];
bool in[1001][501];
int GCD(int x, int y) {//求gcd
if (!x) return y;
if (!y) return x;
return GCD(y, x % y);
}
void add(int x, int y, int z) {//建图
for (int i = 0; i <= 500; i++) {//枚举走之前的gcd值
e[++KK] = (node){z / GCD(i, z), x, i, le[y][GCD(i, z)]}; le[y][GCD(i, z)] = KK;
e[++KK] = (node){z / GCD(i, z), y, i, le[x][GCD(i, z)]}; le[x][GCD(i, z)] = KK;
//
e[++KK] = (node){z / GCD(i, z), y, GCD(i, z), le[x][i]}; le[x][i] = KK;
//
e[++KK] = (node){z / GCD(i, z), x, GCD(i, z), le[y][i]}; le[y][i] = KK;
//
上面这两行是正向的建边，因为要求其他点到一个点的距离，
//
所以可以反向建边然后从n开始跑spfa
}
}
void spfa() {//spfa
memset(dis, 0x7f, sizeof(dis));//初始化
queue <node1> q;
for (int i = 0; i <= 500; i++) {//枚举每一个跑到终点时的状态
q.push((node1){n, i});
in[n][i] = 1;
dis[n][i] = 0;
}
while (!q.empty()) {
node1 now = q.front();
q.pop();
for (int i = le[now.now][now.gcd]; i; i = e[i].nxt) {
int to1 = e[i].to1, to2 = e[i].to2;
if (dis[to1][to2] > dis[now.now][now.gcd] + e[i].x) {
dis[to1][to2] = dis[now.now][now.gcd] + e[i].x;
if (!in[to1][to2]) {
in[to1][to2] = 1;
q.push((node1){to1, to2});
}
}
}
in[now.now][now.gcd] = 0;
}
}
int main() {
scanf("%d %d", &n, &m);//读入
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &z);//读入
add(x, y, z);//建图
}
spfa();//跑spfa
scanf("%d", &qu);//读入
for (int i = 1; i <= qu; i++) {
scanf("%d", &x);//读入
printf("%dn", dis[x][0]);//输出（出发时初始gcd是0）
}
return 0;
}

最后

以上就是谦让黑裤为你收集整理的魔术 魔术 ⁡ \operatorname{魔术} 魔术的全部内容，希望文章能够帮你解决魔术 魔术 ⁡ \operatorname{魔术} 魔术所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。