前言

最短路的奇怪用法

例题引入 洛谷P3403 (opens new window)

AC代码

可以转化成背包大小为$2^{63}$的完全背包问题，保证不会TLE~~

题解：

参考题解 (opens new window)

设三个操作分别可以上升$a, b, c$层且$a\le b \le c$

设$dist[i]$为$\exists x_1,x_2, k=bx_1 + cx_2(k \mod a = i)$的最小整数$k$，即仅通过操作$b/c$能够到达的**对$a$取余等于$i$**的最低楼层

对于第$k$层($k \mod a = i$)，若$dist[i] \ne -1$，即$i$可达，则定有$i+ma \ (m\ge0)$可达

因此只需计算$dist[k]=min(dist[(k-b+a)\%a]+b, dist[(k-c+a)\%a]+c)$

那么答案就可以转化为

$ans=\sum_{0\le i \le a}{\lfloor \frac{h-dist[i]}{a} \rfloor + 1}$

也可以看成是一条有向边$edge(i, (i+b)\%a)$边权$w=b$，$c$同理，转化后跑一遍最短路即可

更多题目

BZOJ 2118 墨墨的等式

悲报：BZOJ倒了

牛客练习赛60 D 斩杀线计算大师

给定$a,b,c,k$，求$ax+by+cz=k$的一组非负整数解（保证有解）。

$1\le a,b,c\le 1e5$

$0\le k \le 1e12$

---

这题正解是拓展欧几里得exgcd，但是由于给了1秒时限，且$mix(a,b,c)\le1e5$，故可以用同余最短路做。

exgcd做法耗时4ms，同余最短路6ms，暴力500ms

AC代码

附录

洛谷P3403 AC代码

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, int> 

using namespace std;

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 1000;

ll dist[maxn];

ll h, x, y, z;

void dij(ll s){
    dist[s] = s;
    priority_queue<pii, vector<pii>, greater<pii> >que;
    que.push({dist[s], s});
    while(!que.empty()){
        ll d = que.top().first, u = que.top().second;
        que.pop();
        if(d != dist[u] || d > h) continue; // 不超过h
        if(dist[(u+y)%x] > dist[u]+y){
            dist[(u+y)%x] = dist[u]+y;
            que.push({dist[(u+y)%x], (u+y)%x});
        }
        if(dist[(u+z)%x] > dist[u]+z){
            dist[(u+z)%x] = dist[u]+z;
            que.push({dist[(u+z)%x], (u+z)%x});
        }
    }
}

int main(){
    cin >> h >> x >> y >> z;
    if(x > y) swap(x, y);
    if(x > z) swap(x, z);
    if(x == 1) {cout << h << endl; return;}
    memset(dist, 0x3f, sizeof dist);
    dij(1);
    ll ans = 0;
    for(int i=0; i<x; i++){
        if(dist[i] > h) continue;
        ans += (h - dist[i])/x + 1;
    }
    cout << ans << endl;
}

牛客练习赛60 D 斩杀线计算大师 AC代码

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, int>  

using namespace std;

const int maxn = 1e5 + 100;

pii config[maxn];
ll dist[maxn], ans[4]={0}, idx[4];
ll a, b, c, k, rem;

bool dij(int target){
	memset(dist, 0x3f, sizeof dist);
	dist[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii> > que;
	que.push({0, 0});
	while(!que.empty()){
		pii info = que.top();
		int u = info.second, tmp;
		que.pop();
		if(u == target) return true;
		if(info.first > dist[info.second]) continue;

		if(dist[tmp=(u+b)%a] > dist[u] + b){
			dist[tmp] = dist[u] + b;
			config[tmp] = {config[u].first + 1, config[u].second};
			que.push({dist[tmp], tmp});
		}

		if(dist[tmp=(u+c)%a] > dist[u] + c){
			dist[tmp] = dist[u] + c;
			config[tmp] = {config[u].first, config[u].second + 1};
			que.push({dist[tmp], tmp});
		}
	}
	return false;
}

signed main(){
	cin >> a >> b >> c >> k;
	for(int i=0; i<4; i++) idx[i] = i;
	if(a > b) swap(a, b), swap(idx[0], idx[1]);
	if(a > c) swap(a, c), swap(idx[0], idx[2]);
	rem = k % a;
	dij(rem);
	ll sum = config[rem].first * b + config[rem].second * c;
	ans[idx[0]] = (k-sum)/a, ans[idx[1]] = config[rem].first, ans[idx[2]] = config[rem].second;
    cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
}