自动搬运

查看原文

来自洛谷，原作者为

	斯德哥尔摩 **

搬运于2025-08-24 21:47:04，当前版本为作者最后更新于2018-08-25 23:49:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3259 [JLOI2014]路径规划

这种题为什么做的人这么少？？？

我来贡献一发题解。

题目大意：

给定一个无向图，每条边有边权，有些点有点权，一些点是加油站。

求一条起点到终点的最短路，使经过有点权的点不超过$k$次，一管油只能走$limit$的时间，时间到了就只能到加油站花$cost$的时间加油。

解法

那个红绿灯的计算公式是$\frac{red^2}{2\times(red+green)}$。

然后把这个时间附加到节点的出边上。

然后，我们建立分层图：

第$i$层表示经过了$i$个红绿灯时，从源点到该点的最短路径长度。

如果没有油量限制，那么我们直接跑最短路就行了。

所以我们考虑如何去掉这个油量限制。

注意到加油站很少，于是我们枚举以每个加油站为起点，向其他加油站经过若干个红绿灯的最短路径。

若此长度不大于最大油量，那么可以直接转移。

我们用这种方法构造新图，依旧是分层图，可是每一层仅有$50$个点，且没有油量限制。

然后就能跑分层图$SPFA$了。

注：不知道为什么，我的$SPFA$要加上$SLF$优化才能过，否则就是#4 $TLE$。

有空就到本蒟蒻的博客里坐坐嘛！

附代码：（我自己都觉得好丑啊。。。）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<string>
#include<deque>
#include<cmath>
#define MAXN 10010
#define MAXM 200010
#define eps (1e-7)
#define MAX (1<<30)//一大堆宏定义
using namespace std;

map<string,int> name;//直接用map存节点编号
int n,m,k,cost,limit,s,t;
int top=0,gas_stack[MAXN],id[MAXN][12];
double length[MAXN];
bool gas[MAXN];

inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}

struct SPFA{
	int c,head[MAXM];
	double path[MAXM];
	bool vis[MAXM];
	SPFA(){c=1;}
	struct Graph{
		int next,to;
		double w;
	}a[MAXM<<2];
	inline int relax(int u,int v,double w){
		if(path[v]>path[u]+w){
			path[v]=path[u]+w;
			return 1;
		}
		return 0;
	}
	inline void add(int u,int v,double w){
		a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
	}
	void spfa(int s){
	    int u,v;
	    deque<int> q;
	    for(int i=1;i<=n*(k+1);i++){path[i]=MAX;vis[i]=false;}
	    path[s]=0;
	    vis[s]=true;
	    q.push_back(s);
	    while(!q.empty()){
	        u=q.front();
	        q.pop_front();
	        vis[u]=false;
	        for(int i=head[u];i;i=a[i].next){
	            v=a[i].to;
	            if(relax(u,v,a[i].w)&&!vis[v]){
	                vis[v]=true;
	                if(!q.empty()){
	                    if(path[v]>path[q.front()])q.push_back(v);
	                    else q.push_front(v);
	                }
	                else q.push_back(v);
	            }
	        }
	    }
	}
}one,two;//旧图和新图

inline void add_edge(int u,int v,int w){//建立分层图
	if(fabs(length[v])>eps)for(int j=0;j<k;j++)one.add(id[u][j],id[v][j+1],w+length[v]);
	else for(int j=0;j<=k;j++)one.add(id[u][j],id[v][j],w);
}
void work(){//求解
	double ans=MAX;
	two.spfa(s);
	for(int i=0;i<=k;i++)ans=min(ans,two.path[t+i*n]);
	printf("%.3lf\n",ans);
}
void init(){//读入+预处理+建分层图
	string x;
	int u,v;
	double w;
	n=read();m=read();k=read();limit=read();cost=read();
    
	for(int i=0;i<=k;i++)
	for(int j=1;j<=n;j++)
	id[j][i]=j+i*n;
    
	for(int i=1;i<=n;i++){
		cin>>x;
		name[x]=i;
		int red=read(),green=read();
		if(x=="start")s=i;
		else if(x=="end")t=i;
		if(x.find("gas")!=string::npos)gas[i]=true;
		if(red)length[i]=1.00*red*red/(double)(2.00*(red+green));
		else length[i]=0;
	}
    
	for(int i=1;i<=m;i++){
		cin>>x;u=name[x];
		cin>>x;v=name[x];
		cin>>x;w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
    
	gas[s]=gas[t]=true;
	for(int i=1;i<=n;i++)if(gas[i])gas_stack[++top]=i;
    
	for(int i=1;i<=top;i++){//旧图与新图的转换
		one.spfa(gas_stack[i]);
		for(int j=1;j<=top;j++){
			if(i==j)continue;
			w=(gas_stack[j]!=s&&gas_stack[j]!=t)?cost:0;
			for(int l=0;l<=k;l++)
			if(one.path[id[gas_stack[j]][l]]<=limit)
			for(int p=0;p+l<=k;p++)
			two.add(id[gas_stack[i]][p],id[gas_stack[j]][p+l],one.path[id[gas_stack[j]][l]]+w);
		}
	}
}
int main(){//主函数So easy!
	init();
	work();
    return 0;
}