HDU 6071 Lazy Running（很牛逼的最短路）

http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意：

1、2、3、4四个点依次形成一个环，现在有个人从2结点出发，每次可以往它相邻的两个结点跑，求最后回到2结点并且不少于K的最短距离。

思路：

官方题解：

最后的答案可以表示为：$ans=p*(2w)+m$，这样一来，m的取值范围就是$(0<=m<2w)$，而因为m的不同，p值也会有所不同。所以我们用 d [ i ] [ m ]表示从起点出发，最后到达 i 点，距离对2w取模为m时的最小距离，这个计算一下最短路即可。

最后只需要枚举m，如果此时d [ 2 ] [ m ]不足K的话，那么就再加上2w补足即可，在所有的m中取最小值。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const ll INF = ;

 const int maxn=1e6+;

 ll k;

 ll m;

 ll d[];

 ll dis[][maxn];

 vector<pll> G[];

 struct HeapNode

 {

     int u; ll w;

     HeapNode(int x, ll y) :u(x), w(y){}

     bool operator <(const HeapNode& rhs) const{

         return w>rhs.w;

     }

 };

 void dijkstra()

 {

     priority_queue<HeapNode> Q;

     for(int i=;i<;i++)

     for(int j=;j<=m;j++)  dis[i][j]=INF;

     Q.push(HeapNode(,));

     while(!Q.empty())

     {

         HeapNode p=Q.top(); Q.pop();

         int u=p.u;

         ll w=p.w;

         for(int i=;i<G[u].size();i++)

         {

             int v=G[u][i].first;

             ll new_w=G[u][i].second+w;

             if(dis[v][new_w%m]>new_w)

             {

                 dis[v][new_w%m]=new_w;

                 Q.push(HeapNode(v,new_w));

             }

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lld",&k);

         for(int i=;i<;i++)  G[i].clear();

         for(int i=;i<;i++)

         {

             scanf("%lld",&d[i]);

             G[i].push_back(make_pair((i+)%,d[i]));

             G[(i+)%].push_back(make_pair(i,d[i]));

         }

         m=*min(d[],d[]);

         dijkstra();

         ll ans=INF;

         for(int i=;i<m;i++)

         {

             ll tmp=k-dis[][i];

             if (tmp<=) ans=min(ans,dis[][i]);

             else ans=min(ans,dis[][i]+(ll)ceil((long double)tmp/m)*m);

         }

         printf("%lld\n",ans);

     }

     return ;

 }