2017年多校赛第四场 1005 Lazy Running（同余最短路）

75 阅读 0 评论 50 点赞

我是靠谱客的博主帅气裙子，最近开发中收集的这篇文章主要介绍2017年多校赛第四场 1005 Lazy Running（同余最短路），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

点击打开链接

题意很简单，就是给出一个距离k，你从2开始跑，可以在四条道路上随便跑，最终回到2，问最短距离是多少。

这是一类经典的取模最短路的题目，在叉姐的网站上面就有这种类型题目的介绍，然而当时看不懂叉姐说啥，现在又有这种类型的题目，看了看别人的博客，觉得算是理解了。

我们怎么考虑这个问题呢？首先，我们可以发现，你完全可以直接在1到2或者2到3的道路上来回多次，这样你最终一定可以回到2。我们既然要来回多次，那肯定是选择两条路比较小的那一条，假设道路长为d，则来回的距离就是m = 2 * d。这里不知道怎么说好。。。我们每次都要让距离对m取模来跑最短路。。。

如果硬要说的话，大概就是，一个五米的环形跑道，你在0的位置，你每次可以跳3米，想要回到原点，你的过程是，0,3,1,4,2,5（也就是0）。此时如果你继续跳是毫无意义的。这就是我们最短路更新的原理，只要这个取模的地方被更新过了，你以后再到这个地方就不可能更新了，因为你的距离已经增加了。

而这道题他跳的距离是变化的，所以不能直接这样取模来做。我们就直接用一个队列，从2出发，到达1得到一个距离，取模更新一下，到达3得到一个距离，取模更新一下。然后继续更新下去。

上面举例也很特殊，因为你跳的距离和跑道的长度的最大公约数是1，如果是按照这道题的样例来看，你可以输出一下就会发现环形跑道的距离是5的倍数，每两个点之间的距离也是5的倍数，所以只会更新余数为5的倍数的距离。

代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<stack>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
ll dis[10][60005];//表示从2出发到达i点且费用对2*w取模结果为j时候的最小花费 
bool vst[10][60005];
ll G[10][10], m, ans, k;
typedef pair<int, ll> pii;

void spfa(int s) {
	memset(dis, 0x3f, sizeof(dis));
	memset(vst, 0, sizeof(vst));
	queue <pii> q;
	q.push(pii(s, 0));//从第二个点，花费为0的位置出发 
	dis[1][0] = 0;//距离的值是一直传递的，但是更新的时候要取模来找位置 
	while(!q.empty()) {
		pii tmp = q.front();
		q.pop();
		int u = tmp.first;
		ll now_dis = tmp.second;
		vst[u][now_dis % m] = 0;
		for(int i = -1; i < 2; i += 2) {
			int v = (u + i + 4) % 4;//只可以去他的上一个点或者下一个点 
			ll next_dis = now_dis + G[u][v];
			if(v == s) { //如果可以回到s，那么就可以更新答案 
				if(next_dis < k) 
					ans = min(ans, next_dis + ((k - 1 - next_dis) / m + 1) * m);//找到一个恰好的位置
				else 															//加上k保证距离大于k 
					ans = min(ans, next_dis);
			}
			if(dis[v][next_dis % m] > next_dis) { 
				dis[v][next_dis % m] = next_dis;
				if(!vst[v][next_dis % m]) {
					vst[v][next_dis % m] = 1;
					q.push(pii(v, next_dis));
				}
			}
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--) {
		memset(G, 0, sizeof(G));
		cin >> k;
		for(int i = 0; i < 4; i++) {
			cin >> G[i][(i + 1) % 4];
			G[(i + 1) % 4][i] = G[i][(i + 1) % 4];
		}
		m = 2 * min(G[0][1], G[1][2]);
		ans = ((k - 1) / m + 1) * m; //先假设一个答案恰好大于k 
		spfa(1);//从第二个点出发回到第二个点，第二个点在G中下标为1 
		cout << ans << 'n';
	}
	return 0;
}