题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意：给你一个由四个节点组成的环，求从节点2出发，回到节点2的不小于k的最短路。

解法：见ICPCCAMP上面这个题：点击打开链接  有叉姐的强力回答。那个题和这个是一样的思路。


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e16;
const int maxn=5;
int T,d1,d2,d3,d4,n,s;
LL k,m;
struct edge{
    int v;
    LL w;
};
vector<edge>g[maxn];
LL dp[4][70000];
void Dijstra(int s){
    priority_queue<pair<LL,int>,vector<pair<LL,int> >, greater<pair<LL, int>> >q;
    for(int i=0; i<4; i++)
    for(int j=0; j<m; j++)
        dp[i][j]=inf;
    dp[s][0]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        LL d=q.top().first;
        int u=q.top().second;
        q.pop();
        if(d>dp[u][d%m]) continue;
        for(int i=0; i<g[u].size(); i++){
            int v=g[u][i].v;
            LL dis = d+g[u][i].w;
            if(dp[v][dis%m]>dis){
                dp[v][dis%m]=dis;
                q.push(make_pair(dis,v));
            }
        }
    }
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        n=4;
        s=1;
        for(int i=0; i<4; i++) g[i].clear();
        scanf("%lld%d%d%d%d",&k,&d1,&d2,&d3,&d4);
        g[0].push_back(edge{1,1LL*d1});
        g[1].push_back(edge{0,1LL*d1});
        g[1].push_back(edge{2,1LL*d2});
        g[2].push_back(edge{1,1LL*d2});
        g[2].push_back(edge{3,1LL*d3});
        g[3].push_back(edge{2,1LL*d3});
        g[3].push_back(edge{0,1LL*d4});
        g[0].push_back(edge{3,1LL*d4});
        m = min(1LL*d1, 1LL*d2) * 2;
        Dijstra(s);
       // puts("***");
        LL ans = 1e19;
        for(int i=0; i<m; i++){
            LL temp = k-dp[1][i];
            if(temp<=0) ans=min(ans,dp[1][i]);
            else ans=min(ans,dp[1][i]+temp/m*m+(temp%m>0)*m);
        }
        printf("%lld\n", ans);
    }
    return 0;
}