当前位置: 代码迷 >> 综合 >> 2017 Multi-University Training Contest - Team 4-hdu 6071 Lazy Running
  详细解决方案

2017 Multi-University Training Contest - Team 4-hdu 6071 Lazy Running

热度:85   发布时间:2023-12-01 22:20:51.0

题目传送门

当时是想到用最短路去做,但是因为本人(太菜)没有想到怎样去实现这个算法(Dijkstra),所以此题也没有做出来(啥也没做出来???),这次HDU的多校让我感觉到自己的实力原来是这么差,看着大佬们AK,自己连一个简单的题目也写不出来,真的很悲伤!看了题解才做出来!!每次都是看题解才做出来,能不能进步一点?(我也想啊)

官方题解:
取w=min(d_{1,2},d_{2,3}),那么对于每一种方案,均可以通过往返跑w这条边使得距离增加2w。也就是说,如果存在距离为k的方案,那么必然存在距离为k+2w的方案。
设dis?i,j表示从起点出发到达i,距离模2w为j时的最短路,那么根据dis?2,j解不等式即可得到最优路线。

时间复杂度O(wlogw)。

那么,这样子考虑为什么可以包含全部的而且最优的解呢?因为我们最后补的是2w或者它的倍数,然后我们把对2w取模后的所有取值的最小花费都计算了一次,这样子得出来的最小花费一定包含所有的情况,即2*w的所有剩余系都被包括了,所以可以保证正确性。

AC代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define F(i,a,n) for(i=a;i<=n;i++)
const int maxn=100000;
typedef long long ll;
typedef pair<ll,int>P;
struct Edge{
    int to;ll distant;Edge(int to_=0,ll distant_=0):to(to_),distant(distant_){
    }
};
vector<Edge>G[maxn];
ll dis[5][maxn];
ll k,n,m;
void Dijkstra()
{
    fill(&dis[0][0],&dis[0][0]+5*maxn,k*2ll);priority_queue<P,vector<P>,greater<P> >que;que.push(P(0ll,2));P p;Edge e;ll w;int u,i;while(!que.empty()){
    p=que.top();que.pop();w=p.first;u=p.second;if(w>dis[u][w%m])continue;F(i,0,G[u].size()-1){
    e=G[u][i];ll dist=w+e.distant;if(dis[e.to][dist%m]>dist){
    dis[e.to][dist%m]=dist;que.push(P(dist,e.to));}}}
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    int i;scanf("%lld",&k);n=4;F(i,1,n)G[i].clear();ll len[4];scanf("%lld%lld%lld%lld",&len[0],&len[1],&len[2],&len[3]);G[1].push_back(Edge(2,len[0]));G[2].push_back(Edge(1,len[0]));G[2].push_back(Edge(3,len[1]));G[3].push_back(Edge(2,len[1]));G[3].push_back(Edge(4,len[2]));G[4].push_back(Edge(3,len[2]));G[4].push_back(Edge(1,len[3]));G[1].push_back(Edge(4,len[3]));m=2*min(len[0],len[1]);Dijkstra();ll ans=2ll*k;F(i,0,m-1){
    ll L=k-dis[2][i];if(L<=0)ans=min(ans,dis[2][i]);else{
    ans=min(ans,dis[2][i]+L/m*m+(L%m>0)*m);//补m的倍数}}printf("%lld\n",ans);}return 0;
}
  相关解决方案