「JLOI2014」路径规划 - 分层图

题目大意

求出从起点到终点经过不超过$k$个红绿灯，同时不加油只能行驶$limit$的时间，加油花费$cost$时间，期望花费的时间。

---

初步想法

如果没有$limit$的限制，这道题就是一道简单的分层图练习题。
首先分析红绿灯，红绿灯的期望时间可以用下图表示：

期望的权值（等待时间）可以用蓝色部分的面积表示：$\frac{red^2}{2}$
碰到绿灯显然权值（等待时间）显然为0，单位概率为：$\frac{1}{red+green}$
故红绿灯的期望为：$\frac{\frac{red^2}{2}}{red+green}$
如果没有$limit$的限制，此题已经解决了。
考虑如果有$limit$的限制，那么必须经过一些加油站。
仔细考虑一下，我们发现除了加油站外的结点对答案的影响可以归到加油站与加油站的距离中。
具体的，将起点与终点标记为加油站，用分层图spfa预处理加油站与加油站间的距离，若该距离（时间）$\le limit$，就将这条边加入第二个分层图，再从起点跑spfa，在各层取个最小值即为答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
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=200005;
struct Edge {
	int from,to;
	double dist;
};
struct Spfa {
	int n,m;
	vector<Edge>edges[maxn];
	bool inque[maxn];
	double dist[maxn];
	void init(int n) {
		this->n=n;
		for(int i=0; i<=n; i++)edges[i].clear();
	}
	void AddEdge(int from,int to,double dist) {
		edges[from].push_back((Edge) {
			from,to,dist
		});
	}
	void main(int s) {
		for(int i=1; i<=n; i++)dist[i]=1e10;
		memset(inque,0,sizeof(inque));
		deque<int>Q;
		Q.push_back(s);
		dist[s]=0;
		inque[s]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop_front();
			inque[Now]=0;
			for(int i=0; i<edges[Now].size(); i++) {
				Edge& e=edges[Now][i];
				int Next=e.to;
				if(dist[Next]>dist[Now]+e.dist) {
					dist[Next]=dist[Now]+e.dist;
					if(!inque[Next]) {
						if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next);
						else Q.push_back(Next);
						inque[Next]=1;
					} 
				}
			}
		}
	}
} G1,G2;
int n,m,deep,limit,cost,cnt=0,Point[15][10005],Start,End,Stands[105];
double Light[10005];
map<string,int>Name;
int dcmp(double x) {
	if(fabs(x)<=1e-8)return 0;
	if(x>1e-8)return 1;
	return -1;
}
void AddEdge(int x,int y,double v) {
	if(dcmp(Light[y])>0)
		for(int j=0; j<deep; j++)G1.AddEdge(Point[j][x],Point[j+1][y],v+Light[y]);
	else
		for(int j=0; j<=deep; j++)G1.AddEdge(Point[j][x],Point[j][y],v);
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m>>deep>>limit>>cost;
	for(int i=0; i<=deep; i++)
		for(int j=1; j<=n; j++)
			Point[i][j]=++cnt;
	for(int i=1; i<=n; i++) {
		string name;
		double red,green;
		cin>>name>>red>>green;
		Name[name]=i;
		if(name=="start") {
			Start=i;
			Stands[++Stands[0]]=i;
		} else if(name=="end") {
			End=i;
			Stands[++Stands[0]]=i;
		} else if(~name.find("gas"))Stands[++Stands[0]]=i;
		if(red==0)Light[i]=0;
		else Light[i]=red*red/(2.0*(red+green)); //期望等待时间 
	}
	G1.init(cnt);
	G2.init(cnt);
	for(int i=1; i<=m; i++) {
		string name;
		cin>>name;
		int x=Name[name];
		cin>>name;
		int y=Name[name];
		double v;
		cin>>name>>v;
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	for(int i=1; i<=Stands[0]; i++) {
		G1.main(Point[0][Stands[i]]);
		for(int j=1; j<=Stands[0]; j++) {
			if(i==j)continue;
			double add=(Stands[j]!=Start&&Stands[j]!=End)?cost:0;
			for(int k=0; k<=deep; k++)
				if(G1.dist[Point[k][Stands[j]]]<=limit)
					for(int p=0; p+k<=deep; p++)
						G2.AddEdge(Point[p][Stands[i]],Point[p+k][Stands[j]],G1.dist[Point[k][Stands[j]]]+add);
		}
	}
	G2.main(Point[0][Start]);  
	double ans=1e10;
	for(int i=0; i<=deep; i++)ans=min(ans,G2.dist[Point[i][End]]);
	printf("%0.3lf\n",ans);
	return 0;
}