【bzoj5047】空间传送装置 堆优化Dijkstra

题目描述

n个点e条边的有向图，每条边是m种类型之一。第i种类型在第x时刻通过所花费的时间为$(a_i*x+b_i)\mod c_i+d_i$。可以在某个点停留。问：在s时刻从1号点出发，到达每个点所花费的最小时间。

输入

第一行包含4个正整数n,m,s,e(2<=n<=100000,1<=m<=50,1<=s<=2000,1<=e<=200000)

分别表示星球的个数、空间传送装置的种类数、当前的时间以及空间传送装置的个数。

接下来m行，每行4个正整数$a_i,b_i,c_i,d_i$(1<=$a_i,b_i,c_i,d_i$<=2000)，依次描述每种装置的参数。

接下来e行，每行3个正整数$u_i,v_i,w_i$(1<=$u_i,v_i$<=n,$u_i$!=$v_i$,1<=$w_i$<=m)

表示从星球$u_i$可以使用第$w_i$种装置单向传送到星球$v_i$。

输出

输出n-1行，每行一个整数，第i行表示从1到i+1的最少所需时间，若无解输出-1。

样例输入

3 2 1 3
1 1 5 1
2 2 7 1
1 2 1
2 3 2
3 1 1

样例输出

3
6

---

题解

堆优化Dijkstra

考虑到如果提前到一个点可以等待，因此先到一定不会比后到劣。所以Dijkstra的贪心策略是正确的。

观察每种边通过所需的时间：$(a_i*x+b_i)\mod c_i+d_i$。因此$x$在模$c_i$意义下只有$c_i$种取值。因此可以先预处理出第$i$种道路在模$c_i$等于$j$的时间下所花费的最小时间。通过求后缀最小值维护即可。（由于关系是一个环，因此可以断环倍增以减少代码量）

然后直接跑堆优化Dijkstra即可。

时间复杂度$O(cm+e\log n)$

#include <queue>

#include <cstdio>

#include <cstring>

#include <utility>

#define N 100010

using namespace std;

typedef pair<int , int> pr;

priority_queue<pr> q;

int a[51] , b[51] , c[51] , d[51] , f[51][4010] , head[N] , to[N << 1] , val[N << 1] , next[N << 1] , cnt , dis[N] , vis[N];

inline void add(int x , int y , int z)

{

	to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

}

int main()

{

	int n , m , s , e , i , j , x , y , z;

	scanf("%d%d%d%d" , &n , &m , &s , &e);

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

	{

		scanf("%d%d%d%d" , &a[i] , &b[i] , &c[i] , &d[i]);

		for(j = 0 ; j < c[i] ; j ++ ) f[i][j] = f[i][j + c[i]] = (a[i] * j + b[i]) % c[i] + d[i];

		for(j = 2 * c[i] - 2 ; ~j ; j -- ) f[i][j] = min(f[i][j] , f[i][j + 1] + 1);

	}

	for(i = 1 ; i <= e ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z);

	memset(dis , 0x3f , sizeof(dis));

	dis[1] = s , q.push(pr(-s , 1));

	while(!q.empty())

	{

		x = q.top().second , q.pop();

		if(vis[x]) continue;

		vis[x] = 1;

		for(i = head[x] ; i ; i = next[i])

			if(dis[to[i]] > dis[x] + f[val[i]][dis[x] % c[val[i]]])

				dis[to[i]] = dis[x] + f[val[i]][dis[x] % c[val[i]]] , q.push(pr(-dis[to[i]] , to[i]));

	}

	for(i = 2 ; i <= n ; i ++ )

	{

		if(dis[i] != 0x3f3f3f3f) printf("%d\n" , dis[i] - s);

		else puts("-1");

	}

	return 0;

}