魔术魔术 ⁡ \operatorname{魔术} 魔术

122 阅读 0 评论 81 点赞

我是靠谱客的博主谦让黑裤，这篇文章主要介绍魔术魔术 ⁡ \operatorname{魔术} 魔术，现在分享给大家，希望可以做个参考。

$魔术$

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

题目

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

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

但是她的法力也是很珍贵的，所以她决定，如果从她的家里出发，到达某个城市所经过的所有路径的权值的最大公约数为 $g$ ，从该城市出发前往下一个城市的路径的权值为 $w$ ，则经过这条路的时候会施法将这条路的路程缩短为 $w g c d ( 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

复制代码

样例输出1

复制代码

样例输入2

复制代码

样例输出2

复制代码

数据范围

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

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

对所有数据:

$2 \leq n \leq 1000$

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

$1 \leq q \leq 1 e 5$

$1 \leq m a x (w) \leq 500$

思路

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

我们看 $n$ 只有 $1000$ ，而且 $m a x (w)$ 最大才 $500$ ，直接反手把一个点拆成 $500$ 个！
（管你傻没傻，反正我是傻了）
然后就每个点拆出来的 $500$ 个点都分别表示到现在路径的 $g c d$ 是多少。
然后就恶心建图跑 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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{魔术} 魔术的全部内容，更多相关魔术内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：# 图论
浏览次数：122 次浏览
发布日期：2024-09-04 21:35:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_f2_13__7_cw.html

魔术魔术 ⁡ \operatorname{魔术} 魔术

$魔术$

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

题目

输入

输出

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

思路

代码

最后

评论列表共有 0 条评论

发表评论取消回复

魔术 魔术 ⁡ \operatorname{魔术} 魔术

魔术 ⁡ operatorname{魔术} 魔术

题目链接： luogu T145393 ⁡ operatorname{luogu T145393} luogu T145393 / SSL比赛 1519 ⁡ operatorname{SSL比赛 1519} SSL比赛 1519

题目

输入

输出

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

思路

代码

最后

微信扫一扫：分享

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

魔术魔术 ⁡ \operatorname{魔术} 魔术

$魔术$

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

发表评论取消回复