HDU 6071 同余最短路

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071
题目大意：有1，2，3，4四个点。是一个环。你可以从i到i+1，i-1。给了你1-2,2-3,3-4,4-5的距离。和一个k。问你从2出发，回到2的>=k的最短路为多少。

思路：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<pair<int, LL> > v[5];
queue<pair<int , LL> > q;
LL dis[5][70005], W;
void SPFA(int u){
    q.push({u, 0}), dis[u][0]=0;
    while(!q.empty()){
        int now=q.front().first; LL nowS=q.front().second; q.pop();
        for(int i=0; i<v[now].size(); i++){
            int to=v[now][i].first; LL w=v[now][i].second;
            //cout<<to<<" "<<w<<endl;
            if(dis[to][(nowS+w)%W]>nowS+w){
                dis[to][(nowS+w)%W]=nowS+w;
                q.push({to, nowS+w});
            }
        }
    }
}

int main(){
    int t; scanf("%d", &t);
    while(t--){
        for(int i=1; i<5; i++) v[i].clear();
        for(int i=1; i<5; i++){
            for(int j=0; j<70005; j++){
                dis[i][j]=1e18+5;
            }
        }
        LL k, d12, d23, d34, d41;
        cin>>k>>d12>>d23>>d34>>d41;
        W=min(d12, d23)*2;

        v[2].push_back({1, d12});
        v[1].push_back({2, d12});
        v[4].push_back({1, d41});
        v[1].push_back({4, d41});
        v[2].push_back({3, d23});
        v[3].push_back({2, d23});
        v[3].push_back({4, d34});
        v[4].push_back({3, d34});
        SPFA(2);
        LL ans=1e18+5;
        for(int i=0; i<W; i++){
            LL d=dis[2][i];
            //cout<<i<<" "<<d<<endl;
            if(d>=k){
                ans=min(ans, dis[2][i]);
            }
            else{
                ans=min(ans, dis[2][i]+((k-dis[2][i]+W-1)/W)*W);
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}