蓝桥杯2018年第九届真题-调手表 最短路

解题思路:可以将题目理解成一张图 同时每条边的长度就是1 并且每个点到其他点的最远距离都是一样的 所以存储了图之后跑一次dijkstra算法即可

注意事项:距离数组初始化成无穷大

参考代码:

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

const int N = 1e5 + 5;

typedef pair<int, int> pii;

priority_queue<pii, vector<pii>, greater<pii>> q;//小根堆 每次弹出距离最近的点

vector<int> m[N];

bool vis[N];

int n, k, dis[N];

//将各个节点转化为一张有向图 因为任意点的最远距离是一样的 跑一次DJ即可

int main()

{   

    cin >> n >> k;

    for (int i = 0; i < n; i++) {

        m[i].push_back((i + 1) % n);

        m[i].push_back((i + k) % n);

    }

    memset(dis, INF, sizeof dis);

    q.push({ 0,0 });

    dis[0] = 0;

    while (!q.empty()) {

        auto temp = q.top(); q.pop();

        int u = temp.second;

        if (vis[u]) continue;

        vis[u] = 1;

        for (int v : m[u]) {

            if (dis[v] > dis[u] + 1) {

                dis[v] = dis[u] + 1;

                q.push({ dis[v],v });

            }

        }

    }

    int ans = *max_element(dis, dis + n);

    cout << ans << endl;

    return 0;

}