路径规划题解
恶心题，加油站怎么都想不到如何处理
所以它先处理加油站之间的不超过k个红绿灯的距离，
再用小于limit的距离见加油站之间的图（转化为到加油站，必加油）
#include<bits/stdc++.h>
using namespace std;
const int N=10002,M=20004,K=12;
const double eps=1e-7;
int n,m,k,s,t,t1,t2,t3,top=0,cnt=0,g[N],head[N*K],head2[N*K];
double a,b,ans=2e18+7,limit,cost,w[N*K],dis[N*K];
struct edge{int nxt,to; double w;}e[(M<<1)*K],f[(M<<1)*K];
struct xd{
double z; int i;
bool operator < (const xd ww) const {return z>ww.z;}
}tmp,nw;
inline void add(int u,int v,double w){e[++cnt].nxt=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;}
inline void add2(int u,int v,double w){f[++cnt].nxt=head2[u],f[cnt].to=v,f[cnt].w=w,head2[u]=cnt;}
inline void add_edge(int u,int v,double www){
if(fabs(w[v])>eps) for(int i=0;i<k;++i) add(i*n+u,i*n+n+v,www+w[v]);
else for(int i=0;i<=k;++i) add(i*n+u,i*n+v,www);
}
map<string,int>name;
string ss,st,sw;
priority_queue<xd> q;
void dijkstra(int x,int hd[],edge o[]){
memset(dis,0x6f,sizeof(dis));
dis[x]=0,tmp.z=0,tmp.i=x,q.push(tmp);
while(!q.empty()){
tmp=q.top(),q.pop();
if(dis[tmp.i]<tmp.z) continue;
for(int i=hd[tmp.i];i;i=o[i].nxt){
nw.i=o[i].to,nw.z=tmp.z+o[i].w;
if(dis[nw.i]>nw.z) dis[nw.i]=nw.z,q.push(nw);
}
}
}
inline int read(){
int T=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
return F*T;
}
int main(){
n=read(),m=read(),k=read(),limit=read(),cost=read();
for(int i=1;i<=n;++i){
cin>>ss,a=read(),b=read(),name[ss]=i;
if(ss=="start") s=i;
if(ss=="end") t=i;
if(ss.find("gas")!=string::npos) ++top,g[top]=i;
if(a) w[i]=a*a/(2.000*(a+b));
}
for(int i=1;i<=m;++i) cin>>ss>>sw>>st,t1=name[ss],t2=name[sw],t3=read(),add_edge(t1,t2,t3),add_edge(t2,t1,t3);
cnt=0,g[++top]=s,g[++top]=t;
for(int i=1;i<=top;++i){
dijkstra(g[i],head,e);
for(int j=1;j<=top;++j){
if(i==j) continue;
a=(g[j]!=s&&g[j]!=t)?cost:0;
for(int p=0;p<=k;++p) if(dis[p*n+g[j]]<=limit) for(int v=0;v+p<=k;++v) add2(v*n+g[i],(p+v)*n+g[j],dis[p*n+g[j]]+a);
}
}
dijkstra(s,head2,f);
for(int i=0;i<=k;++i) ans=min(ans,dis[i*n+t]);
printf("%.3lf",ans);
return 0;
}