相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。考虑到实际情况，一辆车加满油能开的时间有限，所以在地图上增加了几个加油站。

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过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位小数

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<algorithm>#include<queue>#include<map>#include<string.h>using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}    return x*f;}#define MAXN 10010int N,M,K,L,C,Gas[1010],gas,id[15][1100],ID,S,T,pre[MAXN];struct Point{char name[25],id;double Ave; bool re;}p[MAXN];double dist[20][MAXN];struct Graph{    struct EdgeNode{int next,to; double dis;} edge[MAXN*30];    int head[MAXN],cnt;    inline void AddEdge(int u,int v,double w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].dis=w;}    inline void InsertEdge(int u,int v,double w) {AddEdge(u,v,w); AddEdge(v,u,w);}#define Pa pair<int,int>#define Make make_pair#define Di top().first#define Po top().second#define INF (1LL<<60)    double dis[MAXN];    inline void preDijsktra(int st)    {            priority_queue<Pa, vector<Pa> , greater<Pa> > q;        bool visit[21][MAXN]={0};        for (int i=0; i<=K; i++) for (int j=1; j<=N; j++) dist[i][j]=INF;         q.push(Make(0,st)); dist[0][st]=0; visit[0][st]=1;        while (!q.empty())            {                int now=q.Po,D=q.Di; q.pop(); visit[D][now]=0;                for (int i=head[now]; i; i=edge[i].next)                    {                        int tmp=D+(p[edge[i].to].re?1:0);                        if (tmp<=K && dist[D][now]+edge[i].dis+p[edge[i].to].Ave<=L && dist[tmp][edge[i].to]>edge[i].dis+p[edge[i].to].Ave+dist[D][now])                            {                                dist[tmp][edge[i].to]=dist[D][now]+p[edge[i].to].Ave+edge[i].dis;                                if (!visit[tmp][edge[i].to]) q.push(Make(tmp,edge[i].to)),visit[tmp][edge[i].to]=1;                            }                    }            }    }        inline void spfa(int st)    {            queue<int>Q;  bool visit[MAXN];        for (int i=1; i<=ID; i++) dis[i]=INF;        Q.push(st); dis[st]=0.0; visit[st]=1;        while (!Q.empty())            {                int now=Q.front(); Q.pop(); visit[now]=0;                int lay=(now-1)/gas,pos=now%gas; if (!pos) pos=gas;                for (int j=0; j+lay<=K; j++)                    for (int i=head[j*gas+pos],ppp; i; i=edge[i].next)                        {                            ppp=edge[i].to%gas,ppp=!ppp? gas:ppp;                            if (dis[(j+lay)*gas+ppp]>dis[now]+edge[i].dis+C)                                {                                    dis[(j+lay)*gas+ppp]=dis[now]+edge[i].dis+C;                                    if (!visit[(j+lay)*gas+ppp]) Q.push((j+lay)*gas+ppp),visit[(j+lay)*gas+ppp]=1;                                                                    }                        }            }    }} G1,G2;map<string,int>hash;int main(){    freopen("pathplan.in","r",stdin);    freopen("pathplan.out","w",stdout);    N=read(),M=read(),K=read(),L=read(),C=read();    for (int i=1; i<=N; i++)        {            double re,gr;            scanf("%s%lf%lf",p[i].name+1,&re,&gr),p[i].id=i,hash[p[i].name+1]=i;            if (re>0) p[i].re=1,p[i].Ave=(re*re)/2.0/(re+gr);        }    for (int i=1; i<=N; i++)        {            string s=p[i].name+1;            if (s=="start" || s=="end" || s.find("gas")!=string::npos) Gas[++gas]=hash[s],pre[hash[s]]=gas;            if (s=="start") S=hash[s];            if (s=="end") T=hash[s];        }    for (int i=1; i<=M; i++)        {            char u[31],v[31],na[31]; double di;            scanf("%s%s%s%lf",u+1,v+1,na+1,&di);            G1.InsertEdge(hash[u+1],hash[v+1],di);        }    for (int i=0; i<=K; i++)        for (int j=1; j<=gas; j++)            id[i][j]=++ID;    for (int i=1; i<=gas; i++)        {            G1.preDijsktra(Gas[i]);            for (int j=1; j<=gas; j++)                if (i!=j)                    for (int k=0; k<=K; k++)                        if (dist[k][Gas[j]]<INF)                            G2.AddEdge(id[k][i],id[k][j],dist[k][Gas[j]]);                }    G2.spfa(id[0][pre[S]]);    double ans=INF;    for (int i=0; i<=K; i++) ans=min(ans,G2.dis[id[i][pre[T]]]);    printf("%.3lf\n",ans-C);    return 0;}