题目
给定a,b,c,k(1<=a,b,c<=1e5,0<=k<=1e12)，求一组(x,y,z)满足ax+by+cz=k
数据保证一定存在解。如果存在多组解，输出任意一组。
思路来源
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43246478
题解
同余最短路，记mx=max(a,b,c)，
dis[i]表示凑齐与k%mx==i同余的数，所需要的最少值
用最少的值去凑够k%mx的状态dis[k%mx]，显然dis[0]=0,
只要dis[k%mx]足够小（小于k），剩下来的值就可以用若干个mx去凑，
更新dis[k%mx]的过程，是用a、b、c从同余0开始，按最短路的方法更新
因为要输出方案，所以记录了一个前驱nxt，表示是选的哪个数
因为一定有解，递归回去，就找到了各自的个数
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll h,a,b,c,mx,dis[N],num[N];
bool vis[N];
struct node{
ll id,val;//优先队列里记录同余值id,达到该同余值的最小次数val
}nxt[N];//nex实际用于记录前驱同余值id 及当前填的是哪种数(1a 2b 3c)
bool operator<(node a,node b){
return a.val>b.val;
}
priority_queue<node>q;
void dij(){
for(int i=0;i<N;i++){
dis[i]=1e18;
}
dis[0]=0;
q.push((node){0,0});
while(!q.empty()){
int u=q.top().id;q.pop();
if(vis[u])continue;
vis[u]=1;
if(dis[(u+a)%mx]>dis[u]+a){
dis[(u+a)%mx]=dis[u]+a;
nxt[(u+a)%mx]=(node){u,1};
q.push((node){(u+a)%mx,dis[(u+a)%mx]});
}
if(dis[(u+b)%mx]>dis[u]+b){
dis[(u+b)%mx]=dis[u]+b;
nxt[(u+b)%mx]=(node){u,2};
q.push((node){(u+b)%mx,dis[(u+b)%mx]});
}
if(dis[(u+c)%mx]>dis[u]+c){
dis[(u+c)%mx]=dis[u]+c;
nxt[(u+c)%mx]=(node){u,3};
q.push((node){(u+c)%mx,dis[(u+c)%mx]});
}
}
}
void work(int h){
if(h==0)return;
num[nxt[h].val]++;
h=nxt[h].id;
work(h);
}
int main(){
scanf("%lld%lld%lld%lld",&a,&b,&c,&h);
mx=max(a,max(b,c));
dij();
work(h%mx);
int x=a*num[1]+b*num[2]+c*num[3];
x=h-x;
if(mx==a)num[1]+=x/a;
else if(mx==b)num[2]+=x/b;
else if(mx==c)num[3]+=x/c;
for(int i=1;i<=3;++i){
printf("%lld ",num[i]);
}
return 0;
}
