「bzoj5047」空间传送装置 - 最短路径

题目大意

    太空中一共有$n$座星球，它们之间可以通过空间传送装置进行转移。空间传送装置分为$m$种，第$i$种装置可以用$4$个参数$a_i,b_i,c_i,d_i$来描述。因为时空抖动的问题，在非整数时刻禁止使用空间传送装置。如果在整数$s$时刻使用装置，那么需要花费$((a_i\times s+b_i)\bmod c_i)+d_i$单位时间才能完成传送。现在是$s$时刻，小Q位于$1$号星球，请写一个程序计算从$1$号星球到每个星球最少需要的时间。

---

题目分析

不难发现，即使是在模意义下，依然满足越早到达一个结点越优的性质，因此满足Dijkstra的条件。

预处理出在模$c_i$意义下的每个时间经过的最小边权，再跑Dijkstra即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=100005;
struct HeapNode {
	int d,u;
	bool operator < (const HeapNode& b) const {
		return d>b.d;
	}
};
struct Edge {
	int from,to,mod,type;
};
vector<Edge>edges[maxn];
int n,m,s,e,vst[maxn],dist[maxn],val[55][2005],tmp[55];
void AddEdge(int x,int y,int c,int t) {
	edges[x].push_back((Edge) {
		x,y,c,t
	});
}
void Dijkstra() {
	priority_queue<HeapNode>Q;
	for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2;
	memset(vst,0,sizeof(vst));
	dist[1]=s;
	Q.push((HeapNode) {
		s,1
	});
	while(!Q.empty()) {
		int Now=Q.top().u;
		Q.pop();
		if(vst[Now])continue;
		vst[Now]=1;
		for(Edge& e:edges[Now]) {
			int Next=e.to;
			int Dist=val[e.type][dist[Now]%e.mod];
			if(dist[Next]>dist[Now]+Dist) {
				dist[Next]=dist[Now]+Dist;
				Q.push((HeapNode) {
					dist[Next],Next
				});
			}
		}
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	s=Get_Int();
	e=Get_Int();
	for(int i=1; i<=m; i++) {
		int a=Get_Int(),b=Get_Int(),c=Get_Int(),d=Get_Int();
		tmp[i]=c;
		for(int j=0; j<c; j++)val[i][j]=(a*j+b)%c;
		for(int t=1; t<=2; t++) {
			val[i][c]=val[i][0];
			for(int j=c; j>=1; j--)val[i][j-1]=min(val[i][j-1],val[i][j]+1);
		}
		for(int j=0; j<c; j++)val[i][j]+=d;
	}
	for(int i=1; i<=e; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,tmp[v],v);
	}
	Dijkstra();
	for(int i=2; i<=n; i++)
		if(dist[i]==0x7fffffff/2)puts("-1");
		else printf("%d\n",dist[i]-s);
	return 0;
}