hdu 6071 Lazy Running(同余最短路)

题意：

给你4个点，每两个相邻点有一个距离，现在让你在这四个点来回跑步，从2开始，最后回到2，问你找一个距离ans，ans>=k，问最小的ans是多少。

题解：

Claris的官方题解：

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 using ll=long long;
 5 
 6 const int N=6e4+7;
 7 const ll inf=1ll<<61;
 8 int t,v[4],d[5][5],mi;
 9 ll k,dis[5][N],ans;
10 typedef pair<ll,int>P;
11 priority_queue<P,vector<P>,greater<P> >Q;
12 
13 void dijkstra(int s)
14 {
15     F(i,1,4)F(j,0,mi)dis[i][j]=inf;
16     Q.push(P(dis[2][0]=0,2));
17     while(!Q.empty())
18     {
19         ll val=Q.top().first,w;
20         int x=Q.top().second,to,mod;
21         Q.pop(),mod=val%mi;
22         if(val>dis[x][mod])continue;
23         to=x==4?1:x+1;w=dis[x][mod]+d[x][to];
24         if(w<dis[to][w%mi])
25             dis[to][w%mi]=w,Q.push(P(w,to));
26         to=x==1?4:x-1;w=dis[x][mod]+d[x][to];
27         if(w<dis[to][w%mi])
28             dis[to][w%mi]=w,Q.push(P(w,to));
29     }
30 }
31 
32 int main(){
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%lld",&k);
37         F(i,0,3)scanf("%d",v+i);
38         d[1][2]=d[2][1]=v[0];
39         d[2][3]=d[3][2]=v[1];
40         d[3][4]=d[4][3]=v[2];
41         d[1][4]=d[4][1]=v[3];
42         mi=min(v[0],v[1])*2;
43         dijkstra(2),ans=inf;
44         F(i,0,mi)if(dis[2][i]!=inf)
45         {
46             if(dis[2][i]>=k)ans=min(ans,dis[2][i]);
47             else ans=min(ans,(k-dis[2][i]+mi-1)/mi*mi+dis[2][i]);
48         }
49         printf("%lld
",ans);
50     }
51     return 0;
52 }

View Code