相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。考虑到实际情况，一辆车加满油能开的时间有限，所以在地图上增加了几个加油站。
地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过k个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。
（题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油）。
第一行输入5个整数n，m，k，limit，cost，表示有n个点m条边，车能开limit长的时间，及加油所花时间cost。
接下来n行输入每个点信息，包括点的名称（带“gas”的为加油站，“start”为起点，“end”为终点），及该点是否有红绿灯，（a，b表示）（若为a=0则表示没有，a表示红灯长，b表示绿灯长）。
接下来m行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。
保证点和边名的长度不大于20，只有大小写字母，数字及‘_’组成。
一行输出最少平均花费时长。
共14组数据：
其中3组数据，满足n<10，m<20，k<5
另有3组没有红绿灯
所有数据满足n<=10000，m<=20000，k<=10，加油站<=50
答案保留3位小数
题目大意：
给定一个无向图，每条边有边权，有些点有点权，一些点是加油站。
求一条起点到终点的最短路，使经过有点权的点不超过$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;
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(){
init();
work();
return 0;
}
原文：https://www.cnblogs.com/Yangrui-Blog/p/9535892.html