HDU 6071 Lazy Running

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

思路：

取w=\min(d_{1,2},d_{2,3})w=min(d​1,2​​,d​2,3​​)，那么对于每一种方案，均可以通过往返跑$w$这条边使得距离增加$2w$。也就是说，如果存在距离为$k$的方案，那么必然存在距离为$k+2w$的方案。

设dis_{i,j}dis​i,j​​表示从起点出发到达$i$，距离模$2w$为$j$时的最短路，那么根据dis_{2,j}dis​2,j​​解不等式即可得到最优路线。

时间复杂度$O(w\log w)$。

#include<bits/stdc++.h> using namespace std;     #define INF 0x3f3f3f3f3f3f3f3f   #define LL long long     #define fi first     #define se second     #define mem(a,b) memset((a),(b),sizeof(a))        const int MAXN=4+3;   const int MAXM=60000+3;      struct Node   {       int p;       LL dis;       Node(int p, LL d):p(p), dis(d){}   };      LL K, G[MAXN][MAXN], m, ans;   bool vis[MAXN][MAXM];   LL dist[MAXN][MAXM];//从1开始到达i，模m等于j的最短路      void spfa(int s)   {       queue<Node> que;       mem(vis, 0);       mem(dist, 0x3f);       que.push(Node(1, 0));       dist[1][0]=0;       vis[1][0]=true;       while(!que.empty())       {           int u=que.front().p;           LL now_dis=que.front().dis;           vis[u][now_dis%m]=false;           que.pop();           for(int i=-1;i<2;i+=2)           {               int v=(u+i+4)%4;               LL next_dis=now_dis+G[u][v], next_m=next_dis%m;               if(v==s)//形成环，更行答案               {                   if(next_dis<K)                       ans=min(ans, next_dis+((K-next_dis-1)/m+1)*m);                   else ans=min(ans, next_dis);               }               if(dist[v][next_m]>next_dis)               {                   dist[v][next_m]=next_dis;                   if(!vis[v][next_m])                   {                       que.push(Node(v, next_dis));                       vis[v][next_m]=true;                   }               }           }       }   }      int main()   {       int T_T;       scanf("%d", &T_T);       while(T_T--)       {           scanf("%lld", &K);           for(int i=0;i<4;++i)           {               scanf("%lld", &G[i][(i+1)%4]);               G[(i+1)%4][i]=G[i][(i+1)%4];           }           m=2*min(G[1][0], G[1][2]);//最小环           ans=((K-1)/m+1)*m;//只使用最短的回路           spfa(1);           printf("%lld\n", ans);       }              return 0;   }