【2021年省赛B组】试题E: 路径

题解

这题建图方式告诉你了，老老实实按照题目说的方式建图，然后单源最短路$dijkstra$算法一下子就跑出来了。

由于蓝桥杯是闭卷，也就是不让带参考资料，很多人记不住$dijkstra$算法， 后者比赛的时候一紧张就写错了， 导致跑出来的结果差了那么一丢丢，就很尴尬了。考虑这道题目是填空题，那么不需要再规定的时间内完成，那么简单好记的粗暴算法$Floyd$就纳入了我们的选择。

为什么说$Floyd$算法粗暴， 因为他用的是$DP$的思量， 复杂度高达$O(n^3)$，优点就是简单好写。这道题目$n = 2021$， $n^3$约等于$10^{10}$，假设考场的电脑的性能比较差，一秒只能跑$10^8$， 也就我们最多运行100秒，两分钟不到就可以跑出稳妥的答案。

• 最终答案为10266837

提交代码

• $Dijkstra$写法

#include<bits/stdc++.h>
#define int long long

void solve()
{
	std::vector<int> e[2022], w[2022];
	
	for(int i = 1; i <= 2021; i++)
	{
		for(int j = i + 1; j <= 2021; j++)
		{
			if(j - i > 21) continue;
			e[i].push_back(j);
			e[j].push_back(i);
			w[i].push_back(i * j / std::__gcd(i, j));
			w[j].push_back(i * j / std::__gcd(i, j));
		}
	}
	
	std::priority_queue<std::pair<int,int> , std::vector<std::pair<int,int>>, std::greater<std::pair<int,int>>> q;
	std::vector<int> dist(2022, 1e18);
	q.push({0, 1});
	dist[1] = 0;
	std::vector<int> vis(2022);
	vis[1] = 1;
	while(q.size())
	{
		auto t = q.top(); q.pop();
		int dis = t.first;
		int u = t.second;
		
		if(u == 2021)
		{
			std::cout << dist[u] << "\n";
			return;
		}
		
		for(int i = 0; i < e[u].size(); i++)
		{
			int v = e[u][i];
			int W = w[u][i];
			if(vis[v]) continue;
 			if(dist[v] > dist[u] + W)
			{
				dist[v] = dist[u] + W;
				q.push({dist[v], v});
			}
		}
	}
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

• $Floyd$算法

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 3000;
const ll INF = 1e18;
ll mp[maxn][maxn];
void floyd(int n){
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
}
int main(){
    int n = 2021;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j) mp[i][j] = 0;
            else if(abs(i - j) <= 21) mp[i][j] = mp[j][i] = i * j / __gcd(i, j);
            else mp[i][j] = mp[j][i] = INF;
        }
    }
    floyd(n);
    cout << mp[1][2021];
    return 0;
}