HDU 6071 Lazy Running (最短路)

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6071

题解

又是一道虐信心的智商题。。。

首先有一个辅助问题，这道题转化了一波之后就会化成这个问题: 给定(a_1,a_2,...,a_n)和(K)，求使得(sum^{n}_{i=1}a_ix_i=B)有正整数解且(Bge K)的最小(B)值。在本题中(n=4, a_ile 30000, Kle 10^{18}).
这好像是个最短路经典问题，但是我想了三小时根本没想到做法……
大概是随便找一个(a_k)(一般来说找最小值节省常数)然后对于模(a_k)剩余系下每个数建一个点，每个数(t)向((t+a_i)mod a_k (i=1,2,...,n))连边，这样从(1)到(j)的最短路就是模(a_k)余(j)的最小(B). 这样就可以在(O(na_ilog n))的时间内解决上述问题。
下面我们把这个问题({ a_i} ={ d_i},K=x)的答案记作(f(x)).

然后考虑原问题如何转化为上述问题，我和题解的转化方式不同。
下面是我的方法（我觉得没啥问题，但是这题数据确实挺弱，有问题欢迎提出啊）：
设(d_1,d_2,d_3,d_4)分别是(1,2,3,4)连向编号下一个的点的边权，我们可以将从(2)点出发回到(2)点的路径分为五种:

(1) 从(2)到(1)再回来，长度(2d_1).

(2) 从(2)到(3)再回来，长度(2d_2).

(3) 从(2)到(3)再到(4), 到(1)或者不到(1), 再回来。
此时(d_2)边恰好经过往返各一次，(d_3)边往返至少一次（防止出现不经过(d_3)直接去(d_4)的不合法情况），(d_4)边往返次数任意，长度(2d_2+2d_3+2k_3d_3+2k_4d_4) ((k_3,k_4)为任意非负整数)

(4) 从(2)到(1)再到(4), 到(3)或者不到(3), 再回来。与上一种情况对称，长度(2d_1+2d_4+2k_3d_3+2k_4d_4) ((k_3,k_4)为非负整数)

(5) 走一个环，环上的边可以额外往返任意多次。长度(d_1+d_2+d_3+d_4+k_1d_1+k_2d_2+k_3d_3+k_4d_4) ((k_1,k_2,k_3,k_4)为非负整数)
现在考虑简化以上讨论：(3)和(4)各做一次与做两次(5)等价，(5)做多于一次与做一次等价(因为做多次就相当于给(k)增加值)，因此可以认为(5)至多做一次。
如果(1)(5), (2)(5)同时做都没有意义，(1)(3), (2)(4)同时做相当于做了(5)也没有意义。
考虑最优策略:

(1) 如果(5)做一次，那么(3)和(4)都没有必要做了，因为(3)和(4)的操作就相当于给(5)中的(k)增加值。于是这一部分的答案就是(f(n-d_1-d_2-d_3-d_4)+d_1+d_2+d_3+d_4).

(2) 如果(5)不做，那么(3)和(4)中可以做一个，这一部分的答案是(min(f(n-2d_1-2d_4)+2d_1+2d_4,f(n-2d_2-2d_3)+2d_2+2d_3)).

(3) 如果(3)(4)(5)都不做，那么考虑(1)和(2)，这一部分应该是等于上述问题(n=2, a_1=d_1,a_2=d_2,K=n)时的答案。
时间复杂度(O(dlog d)), 详细一点大概是(ShortestPath(d,4d)+ShortestPath(d,2d)).
这个样写可能唯一的好处就是常数比较小吧……

下面是题解的做法：
把剩余系的模数设为(min(d_1,d_2)), 然后设(f[i][j])表示在(i)这个点余数是(j)的答案，然后类似最短路转移DP的方法来求。
时间复杂度(O(dlog d)), 详细一点大概是(ShortestPath(4d,8d)).

代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define llong long long
using namespace std;
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
const int N = 6e4;
const int M = 1.2e5;
const llong INF = 1000000000000200000ll;
struct Edge
{
int v,nxt; llong w;
} e[(M<<1)+3];
int fe[N+3];
struct DijNode
{
int u; llong x;
DijNode() {}
DijNode(int _u,llong _x) {u = _u,x = _x;}
bool operator <(const DijNode &arg) const {return x>arg.x;}
};
priority_queue<DijNode> pq;
llong dis[N+3];
bool vis[N+3];
llong d[5],x;
int n,en;
void addedge(int u,int v,llong w)
{
en++; e[en].v = v; e[en].w = w;
e[en].nxt = fe[u]; fe[u] = en;
}
void Dijkstra()
{
memset(dis,30,sizeof(dis)); memset(vis,0,sizeof(vis));
dis[0] = 0ll; pq.push(DijNode(0,0ll));
while(!pq.empty())
{
DijNode tmp = pq.top(); pq.pop(); int u = tmp.u;
if(tmp.x!=dis[u]) continue;
if(vis[u]) continue;
vis[u] = true;
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v;
if(dis[v]>dis[u]+e[i].w && vis[v]==false)
{
dis[v] = dis[u]+e[i].w;
pq.push(DijNode(v,dis[v]));
}
}
}
}
void clear()
{
for(int i=0; i<=en; i++) e[i].v = e[i].w = e[i].nxt = 0;
for(int i=0; i<=n; i++) fe[i] = 0;
en = n = 0;
}
llong solve(llong x)
{
if(x<0) return 0ll;
llong ret = x;
while(dis[ret%n]>ret) ret++;
return ret;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld%lld",&x,&d[1],&d[2],&d[3],&d[4]);
llong ans = INF,tmp;
n = min(min(d[1]+d[1],d[2]+d[2]),min(d[3]+d[3],d[4]+d[4]));
for(int i=0; i<n; i++)
{
for(int j=1; j<=4; j++)
{
addedge(i,(i+d[j]+d[j])%n,d[j]+d[j]);
}
}
Dijkstra();
tmp = solve(x-d[1]-d[2]-d[3]-d[4])+d[1]+d[2]+d[3]+d[4]; ans = min(ans,tmp);
tmp = solve(x-d[1]-d[1]-d[4]-d[4])+d[1]+d[1]+d[4]+d[4]; ans = min(ans,tmp);
tmp = solve(x-d[2]-d[2]-d[3]-d[3])+d[2]+d[2]+d[3]+d[3]; ans = min(ans,tmp);
clear();
n = min(d[1]+d[1],d[2]+d[2]);
for(int i=0; i<n; i++)
{
for(int j=1; j<=2; j++)
{
addedge(i,(i+d[j]+d[j])%n,d[j]+d[j]);
}
}
Dijkstra();
tmp = solve(x); ans = min(ans,tmp);
clear();
printf("%lldn",ans);
}
return 0;
}