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

​​题目传送门​​

当时是想到用最短路去做，但是因为本人（太菜）没有想到怎样去实现这个算法（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)。

#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;
}