链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071
挺晚了，还是决定写一下题解~~~
题意：给你四个点，组成一个圈，求从2出发再回到2的所有路径中大于K的最小值；
思路：其实跟前一篇大容量背包一样利用同余系最短路求；
可以这么理解，我对满足要求的所有路径分类，标准是模m的值为j(0=<j<m)的所有路径分到一组，而dis[i][j]表示满足从1到i模m为j的最小
路径，因为我们求的是最短路径，对于一组同余系，我记录最小的解即可，m是从1出来的两条边中最短的那条边的二倍，之所以是二倍
，因为我要满足一个环，使原来的解加上一个环依旧是一个解，最后把dis[1][0~m-1]的数都变成大于k得数，从中取最小值即可；为什么
结果一定是正解呢？因为发现在这我把所有的解变成了dis[1][0~m-1]+x*m的形式了，那我从dis[1][0~m-1]出发，一定可以找到解空间的
所有情况，那我找出来的最小值必然是正解了；
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef long long LL; const int maxn=6e4+10; bool vis[5][maxn]; LL dis[5][maxn],G[5][5]; struct node { int p,j; node(int _p,int _j):p(_p),j(_j){} }; void spfa(int s,int m) { memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); queue<node>q; q.push(node(1,0)); dis[1][0]=0; vis[1][0]=true; while(!q.empty()) { node tn=q.front(); q.pop(); int v=tn.p,j=tn.j; vis[v][j]=false; for(int i=-1;i<2;i+=2) { int tv=(v+i+4)%4; LL d=dis[v][j]+G[v][tv]; if(dis[tv][d%m]>d) { dis[tv][d%m]=d; if(!vis[tv][d%m]) { q.push(node(tv,d%m)); vis[tv][d%m]=true; } } } } } int main() { //freopen("input.txt","r",stdin); int T; for(scanf("%d",&T);T;T--) { LL k;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]; } int m=2*min(G[1][0],G[1][2]); spfa(1,m); LL ans=((k-1)/m+1)*m; for(int i=0;i<m;i++) { LL tmp=dis[1][i]>k?dis[1][i]:((k-dis[1][i]-1)/m+1)*m+dis[1][i]; ans=min(ans,tmp); } printf("%lld ",ans); } return 0; }