首先計(jì)算在紅綠燈 \((a,b)\) 處期望的等待時(shí)間。記 \(a+b\) 為一個(gè)周期（即先有時(shí)長為 \(a\) 的紅燈，再有時(shí)長為 \(b\) 的綠燈），設(shè)我們?cè)?\(x\) 時(shí)刻到達(dá)了這個(gè)紅綠燈，那么我們需要等待的時(shí)間顯然為 \(\max(a-x,0)\)。

要求出期望，就要用上面那個(gè)函數(shù)的和再除以總時(shí)長，也就是 \(\frac{a^2}{2(a+b)}\)。于是這道題就變成了一道普通的圖論問題。

考慮分層圖，一共建 \(k+1\) 層圖，在每個(gè)紅綠燈處向上一層連邊。考慮答案路徑，一定是從起點(diǎn)開始再若干個(gè)加油站加油再走到終點(diǎn)的過程，而加油站與加油站之間怎么走我們是不用管它的。那么我們就以每個(gè)加油站為起點(diǎn)跑最短路，將所有加油站抽出來，在限制內(nèi)能走到另一個(gè)加油站就在新圖上連邊。最后再在新圖上跑一次最短路即可。

時(shí)間復(fù)雜度 \(O(50kn\log kn)\)。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define id(x,y) ((x)+n*((y)-1))
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,_k,lim,cst;
double dis[maxn],out[maxn];
bool gas[maxn],vis[maxn];
map<string,int> hao;
vector<pair<int,double> > e1[maxn],e2[maxn];
priority_queue<pair<double,int> > q;
il void dijkstra(int s,auto &e){
	for(int i=1;i<=n*(_k+1);i++){
		dis[i]=1e18,vis[i]=0;
	}
	dis[s]=0,q.push(mp(0,s));
	while(q.size()){
		int u=q.top().sec;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(auto i:e[u]){
			int v=i.fir;
			double w=i.sec;
			if(!vis[v]&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(mp(-dis[v],v));
			}
		}
	}
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>_k>>lim>>cst;
	for(int i=1,a,b;i<=n;i++){
		string s;
		cin>>s>>a>>b;
		hao[s]=i;
		gas[i]=~s.find("gas");
		if(a){
//			cout<<i<<"\n";
			out[i]=a*1.0*a/2/(a+b);
		}
	}
	int st=hao["start"],ed=hao["end"];
	for(int i=1,u,v,w;i<=m;i++){
		string a,b,c;
		cin>>a>>b>>c>>w;
		u=hao[a],v=hao[b];
		for(int j=1;j<=_k+1;j++){
			if(out[u]){
				if(j<=_k){
					e1[id(u,j)].pb(mp(id(v,j+1),w+out[u]));
				}
			}
			else{
				e1[id(u,j)].pb(mp(id(v,j),w));
			}
			if(out[v]){
				if(j<=_k){
					e1[id(v,j)].pb(mp(id(u,j+1),w+out[v]));
				}
			}
			else{
				e1[id(v,j)].pb(mp(id(u,j),w));
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(i==st||gas[i]){
//			cout<<i<<"---";
			dijkstra(i,e1);
			for(int j=1;j<=n;j++){
				if(gas[j]){
					for(int k=1;k<=_k+1;k++){
						if(dis[id(j,k)]<=lim){
							for(int x=1,y=k;y<=_k+1;x++,y++){
								e2[id(i,x)].pb(mp(id(j,y),dis[id(j,k)]+cst));
//								cout<<id(i,x)<<" "<<id(j,y)<<" "<<dis[id(j,k)]+cst<<"\n";
							}
						}
					}
				}
				else if(j==ed){
					for(int k=1;k<=_k+1;k++){
						if(dis[id(j,k)]<=lim){
							for(int x=1,y=k;y<=_k+1;x++,y++){
								e2[id(i,x)].pb(mp(id(j,y),dis[id(j,k)]));
//								cout<<id(i,x)<<" "<<id(j,y)<<" "<<dis[id(j,k)]<<"\n";
							}
						}
					}
				}
			}
		}
	}
	dijkstra(st,e2);
	double ans=1e18;
	for(int i=1;i<=_k+1;i++){
//		cout<<dis[id(ed,i)]<<"\n";
		ans=min(ans,dis[id(ed,i)]);
	}
	printf("%.3f",ans);
	return 0;
}
}
int main(){return asbt::main();}