[Dijkstra] Hdu P6071 Lazy Running

题解

• 我们取w=min(a,b)，那么如果存在一种路径长度为k，那么肯定存在一种长度为k+2w
• 那么我们就可以dis[i][j]表示从起点出发到达i，距离模2w为j的最短路，然后跑Dijkstra得出dis数组
• 最后根据dis[2][j]解不等式就好了

代码

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
const ll N=1000010,inf=2e18;
typedef pair<ll,int>node; 
priority_queue<node,vector<node>,greater<node> >Q;  
struct edge {int to,from;ll w;}e[N];
ll w,ans,k,a,b,c,d,dis[5][N];
int T,cnt,head[N];
void insert(int x,int y,ll w)
{
    e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].w=w;
    e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].w=w;
}
void dijkstra(ll s)
{
    for (ll i=0;i<=4;i++) for (ll j=0;j<w;j++) dis[i][j]=inf;
    Q.push(make_pair(0ll,s));
    while (!Q.empty())
    {
        ll x=Q.top().first;int y=Q.top().second; Q.pop();
        if (x>dis[y][x%w]) continue;
        for (int i=head[y];i;i=e[i].from)
        {
            ll xx=x+e[i].w;
            if (dis[e[i].to][xx%w]>xx) dis[e[i].to][xx%w]=xx,Q.push(make_pair(xx,e[i].to));
        }
    }
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(head,-1,sizeof(head)),scanf("%lld%lld%lld%lld%lld",&k,&a,&b,&c,&d),ans=inf,cnt=0;
        w=2*min(a,b);
        insert(1,2,a),insert(2,3,b),insert(3,4,c),insert(1,4,d),dijkstra(2);
        for (ll i=0;i<w;i++) if (k<=dis[2][i]) ans=min(ans,dis[2][i]); else ans=min(ans,dis[2][i]+((k-dis[2][i]+w-1)/w)*w);
        printf("%lld
",ans);
    }
}