HDU 6071 Lazy Running 同餘 + 最短路

傳送門：HDU6071

題意：給你一個由四個節點組成的環，相鄰兩點間可達，求從節點2出發，回到節點2的不小于k的最短路徑的長度。

思路：

先擺上官方題解：

​​

取w=\min(d_{1,2},d_{2,3})w=min(d​1,2​​,d​2,3​​)，那麼對于每一種方案，均可以通過往返跑ww這條邊使得距離增加2w2w。也就是說，如果存在距離為kk的方案，那麼必然存在距離為k+2wk+2w的方案。

設dis_{i,j}dis​i,j​​表示從起點出發到達ii，距離模2w2w為jj時的最短路，那麼根據dis_{2,j}dis​2,j​​解不等式即可得到最優路線。

時間複雜度O(w\log w)O(wlogw)。

也就是說，假設我們将任意一條長度大于k的回路（從2出發回到2）成為可行路徑，那麼任意一條可行路徑加上2w一定還是一條可行路徑，所有可行路徑中，最短的是k，最長的為 k + 2 * n * w,(n趨近正無窮),顯然我們不可能求出所有的可行路徑來，由于所有可行路徑長度中都含有2w（有可能含0個），我們可以考慮按對2w的餘數分塊，這樣我們隻要求出%2w == 0的最短可行路徑，%2w == 1的最短可行路徑。。。一直到%2w == 2w - 1的最短可行路徑，然後在這2w條可行路徑中找一條最短的就是答案了（因為這條一定是所有可行路徑中最短的那條）

然後問題就是如何求出%2w同餘的所有可行路徑中最短的那條了，用dis[i][j]表示從2号點出發到達i，長度%2w為j的最短路徑的長度（注意這裡不一定是可行路徑，長度可以小于K，因為我們可以最後再添幾個2w使其剛好大于K，并且添加2w以後并不會改變其長度%2w == j的性質），這個數組可以用dijkstra的思想求出來，注意要加堆優化。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
#define inf 0x3f3f3f3f3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
using namespace std;
typedef pair<ll,int>P;
const int MAXN=100010;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
priority_queue<P, vector<P>, greater<P> > q;
struct node{
	int v, w;
	node(){}
	node(int _v, int _w) : v(_v), w(_w){}
}g[5][2];
ll dis[5][60060];
void dijkstra(int k)
{
	memset(dis, inf, sizeof(dis));
	dis[2][0] = 0;
	q.push(P(0, 2));
	while(!q.empty())
	{
		P u = q.top(); q.pop();
		if(u.fi > dis[u.se][u.fi % k]) continue;
		for(int i = 0; i < 2; i++)
		{
			ll w = u.fi + g[u.se][i].w;
			int v = g[u.se][i].v;
			if(dis[v][w % k] > w)
			{
				dis[v][w % k] = w;
				q.push(P(w, v));
			}
		}
	}
}
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		ll k;
		scanf("%lld %d %d %d %d", &k, &g[1][0].w, &g[2][0].w, &g[3][0].w, &g[4][0].w);
		g[1][0].v = 2;
		g[2][0].v = 3;
		g[3][0].v = 4;
		g[4][0].v = 1;
		g[1][1] = node(4, g[4][0].w);
		g[2][1] = node(1, g[1][0].w);
		g[3][1] = node(2, g[2][0].w);
		g[4][1] = node(3, g[3][0].w);
		int w = min(g[1][0].w, g[2][0].w) * 2;
		dijkstra(w);
		ll ans = inf, tmp;
		for(int i = 0; i <= w; i++)
		{
			if(dis[2][i] > k)
			ans = min(ans, dis[2][i]);
			else
			{
				tmp = (k - dis[2][i]) / w * w + dis[2][i];
				if((k - dis[2][i]) % w)
				tmp += w;
				ans = min(ans, tmp);
			}
		}
		cout << ans << endl;
	}
 	return 0;
}