蓝桥杯省赛的题目

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dis[505][505];
const int inf = 99999999;
int main()
{
int n;cin>>n;
for(int i=1; i<=n;i++)
for(int j=1;j<=n;j++)
if(abs(i-j) <= 21) dis[i][j] = i*j/ gcd(i,j);
else dis[i][j] = inf;

for(int k=1; k<=n; k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(dis[i][k]+dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k]+dis[k][j];
}
cout<<dis[1][n];
}

今年蓝桥杯省赛的题目。

最短路有多种做法，根据数据范围的不同可以有多种选择。

以下不讨论负环情况，因为负环图没有最短路。

（1） floyd算法， 可以求图中任意两点的最短路，时间复杂度\(O(n^3)\)，\(n\)表示图中点的个数

（2） dijkstra算法，可以求一个源点到任意一点的最短路，朴素的dijkstra时间复杂度\(O(n^2)\)，通过堆优化后，可以达到\(O((n+m) \log n)\), \(n\)表示图中点的个数,\(m\)表示图中边的数量。

（3） bellman-ford算法，可以求一个源点到任意一点的最短路，最坏时间复杂度是\(O(nE)\)，n是点的个数，E是图中边的数量。

（3-1） SPFA算法， 是bellman-ford算法的队列优化版本，最坏时间复杂度仍然是\(O(nE)\)，但在一般情况下，往往能达到\(O(kE)\)的效果，其中\(k\)是很小的常数。
SPFA算法的发明者在其论文中证明了在任意时刻SPFA算法的复杂度都是\(O(kE)\)，但后人发现论文的证明是错误的。

（4）Johnson 全源最短路算法， 可以求任意两点的最短距离， 时间复杂度\(O(n^2 \log n)\)

顺便一提，对于\(40\%\)的数据，直接输出\(n\)即可。

对于本题而言，使用任意一种算法都是可以通过的。下面给出最好写的\(floyd\)算法：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dis[505][505]; 
const int inf = 99999999;
int main()
{
    int n;cin>>n;
    for(int i=1; i<=n;i++)
        for(int j=1;j<=n;j++)
            if(abs(i-j) <= 21) dis[i][j] = i*j/ gcd(i,j);
            else dis[i][j] = inf;
    
    for(int k=1; k<=n; k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(dis[i][k]+dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k]+dis[k][j];
            }
    cout<<dis[1][n];
}