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

解题思路:

注意事项:

求最优策略步数，可以将问题建模成图，然后利用最短路来解决。对于 n−1 以内的每一个数字 i，我们可以将 i 向 n+1 mod n 和 n+k mod n 各连一条边权为 1 的有向边，表示数字 i 经过一次操作可以变为 i+1 mod n 或 n+k mod n，然后以 0 为起点跑一遍最短路，最终得到的每一个数字的最短路径即为最少操作数，取其中最大的输出即可。

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
const ll N=2e5+5;
struct node{
	ll id,dis;
	bool operator<(const node& x)const{
		return x.dis<dis;
	}
};
vector<node> v[N];
ll n,k,w[N],kkk=-1e9;
bool vis[N];
void dij(){
	priority_queue<node> q;
	memset(w,0x3f,sizeof w);
	q.push({0,0});
	w[0]=0;
	while(!q.empty()){
		node x=q.top();q.pop();
		if(vis[x.id])continue;
		vis[x.id]=true;
		for(auto i:v[x.id]){
			if(w[i.id]>w[x.id]+i.dis){
				w[i.id]=w[x.id]+i.dis;
				q.push({i.id,w[i.id]});
			}
		}
	}
}
int main(){
	cin>>n>>k;
	for(ll i=0;i<n;i++){
		ll x1=(i+1)%n,x2=(i+k)%n;
		v[i].push_back({x1,1});
		v[i].push_back({x2,1});
	}
	dij();
	for(ll i=0;i<n;i++)kkk=max(w[i],kkk);
	cout<<kkk<<endl;
	return 0;
}