做网站，就上凡科建站,做外汇 虚拟网站,微小店网站建设口碑好,做游戏网站需要注意的问题路径 - 蓝桥云课 (lanqiao.cn) 题目分析
求最短路问题#xff0c;有多种解法#xff0c;下面介绍两种蓝桥杯最常用到的两种解法
方法一
Floyd#xff08;求任意两点之间的最短路#xff09;注#xff1a;不能有负权回路
初始化每个点到每个点的距离都为0x3f这样才能对… 路径 - 蓝桥云课 (lanqiao.cn) 题目分析
求最短路问题有多种解法下面介绍两种蓝桥杯最常用到的两种解法
方法一
Floyd求任意两点之间的最短路注不能有负权回路
初始化每个点到每个点的距离都为0x3f这样才能对比求出最短路
由题意先将ab差的绝对值小于等于21的边的边权赋予还有自己到自己的边为0
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 3000;
int ans 0x3f;
int d[N][N];
int gcd(int a, int b)
{return b 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{return a * b / gcd(a, b);
}
int main()
{ memset(d, 0x3f, sizeof d);for(int i 1; i 2021; i ){for(int j 1; j 2021; j ){if(abs(i - j) 21){d[i][j] min(d[i][j], lcm(i, j));}}}for(int i 1; i 2021; i )d[i][i] 0;for(int k 1; k 2021; k ){for(int i 1; i 2021; i ){for(int j 1; j 2021; j ){d[i][j] min(d[i][j], d[i][k] d[k][j]);}}}cout d[1][2021];return 0;
}
答案10266837
方法二
Dijkstra任意一点到所有点的最短路
第一步初始化距离 dist[1] 0, dist[i] ∞
第二步找到当前没有确定点的最小值找到最小的点之后用这个点去更新它到所有点的距离 #includebits/stdc.h
using namespace std;
typedef long long ll;
typedef pairint, int PII;
const int N 2e5 10;
int e[N], ne[N], w[N], h[N], idx, d[N];
bool st[N];
int gcd(int a, int b)
{return b 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{return a * b / gcd(a, b);
}
void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}
int dijkstra()
{memset(d, 0x3f, sizeof d);d[1] 0;priority_queuePII, vectorPII, greaterPII q;q.push({0, 1});while(q.size()){auto t q.top();q.pop();int num t.second, dis t.first;if(st[num])continue;st[num] true;for(int i h[num]; i ! -1; i ne[i]){int j e[i];if(d[j] dis w[i]){d[j] dis w[i];q.push({d[j], j});}}}//if(d[2021] 0x3f3f3f3f)return -1;return d[2021];
}
int main()
{ memset(h, -1, sizeof h);for(int i 1; i 2021; i ){for(int j 1; j 2021; j ){if(abs(i - j) 21){add(i, j, lcm(i, j));}}}cout dijkstra();return 0;
}
