意甲冠军：要查找。有门户网站：http://www.lydsy.com/JudgeOnline/problem.php?

id=3627

注意：点的等待时长示意图为：

非常清晰了吧？没事，不清晰就不清晰吧。反正公式给你了，这不是本题知识点。扒即可了。

题解：

看到这题的数据范围。我们就想到了分层图。但是如今有两种须要分层的东西：剩余油量的限制。和经过红绿灯的限制。所以我们要搞掉当中一个，使题目转化成分层图。红绿灯限制非常不好惹的样子，所以我们还是把剩余油量的限制搞掉吧。

怎么搞掉油量的限制呢？我们能够把整个图缩成一个仅仅有加油站的图，这样两加油站之间仅仅要能够直接到达，就不用再管【剩余油量】了！

当然，起点和终点也要算到加油站中，至于终点可能多加的一份【加油费用】。再删掉就好了~

详细做法：非常easy地说。。枚举每一个加油站，看满油从它出发能跑到哪些点，然后建边（新图的边，点为加油站的图的边）。而两点之间依据经过红绿灯的不同。所以可能有多条边。

。再简单一点的说法就是——看下述代码！

！

好了，新图建好了，跑一遍水水的分层图吧。

就是dist[i][j]表示到j时经过i个红绿灯的最短路径，至于若j有红灯时算不算上神马的就不用写得太拘束了，爱怎么写怎么写。题目到这里已经非常水了。

。

注意：

我们在预处理节点名称的时候最好还是建一棵字典树。这样找起来会非常快。代码也非常好写。

不然可能就须要写一发pq优化的nlogn最短路。哪个好写，自己想吧。另。假设想刷rank。这两个都得写！！！

假设不会分层图的话。最好还是看看这一篇：http://blog.csdn.net/vmurder/article/details/40075989

好了。直接贴代码，写得比較清晰，仅仅是由于代码量的缘故才会看着发晕。认真细致一点非常easy看懂（大不了你用例子数据手调一下我的代码！不信看不懂！

）

（原题数据范围错了，n和m都应该是原来的2倍。）

/**************************************************************

    Problem: 3627

    User: 18357

    Language: C++

    Result: Accepted

    Time:716 ms

    Memory:69628 kb

****************************************************************/

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 10100

#define M 20100

#define P 60

#define TT 80

#define eps 1e-7

#define inf 0x3f3f3f3f

using namespace std;

/*i won't tell you it's a trie. */

struct Trie

{

    int next[N*20][TT],cnt;

    int note[N*20],sign;

    char s[TT];

    inline int insert()

    {

        scanf("%s",s+1);

        int x=0,i,alp;

        for(i=1;s[i];i++)

        {

            alp=s[i]-'0';

            if(!next[x][alp])next[x][alp]=++cnt;

            x=next[x][alp];

        }

        if(!note[x])note[x]=++sign;

        return note[x];

    }

    inline int judge()

    {

        for(int i=1;s[i];i++)if(i>=5&&s[i]=='t'&&s[i-1]=='r'&&s[i-2]=='a'&&s[i-3]=='t'&&s[i-4]=='s')return 1;

        for(int i=1;s[i];i++)if(i>=3&&s[i]=='s'&&s[i-1]=='a'&&s[i-2]=='g')return 2;

        for(int i=1;s[i];i++)if(i>=3&&s[i]=='d'&&s[i-1]=='n'&&s[i-2]=='e')return 3;

        return 0;

    }

}trie;

/*for original graph or prespfa or the gas_station graph. */

struct KSD

{

    int u,v,next;

    double len;

}e[M<<1],E[15][P*P<<1];

int head[N],cnt;

void add(int u,int v,double len)

{

    cnt++;

    e[cnt].u=u;

    e[cnt].v=v;

    e[cnt].len=len;

    e[cnt].next=head[u];

    head[u]=cnt;

}

int HEAD[15][P],CNT[15];

void ADD(int light,int u,int v,double len)

{/*i feel sick for my code here, but i can't do anything. */

    CNT[light]++;

    E[light][CNT[light]].u=u;

    E[light][CNT[light]].v=v;

    E[light][CNT[light]].len=len;

    E[light][CNT[light]].next=HEAD[light][u];

    HEAD[light][u]=CNT[light];

}

struct Lux

{

    int x,y;

    Lux(int _x,int _y):x(_x),y(_y){}

    Lux(){}

};

queue<Lux>q;

double dist[15][N];

bool in[15][N];

/*for static code*/

int n,m,lig,gas,cost;

/*for each point*/

bool red[N];

int sta[N];

double ave[N];

int gas_station[N],num;

/*for temp input*/

char ttt[TT];

void prespfa(int S)

{/*build the direct combinations between the gas_stations. */

    while(!q.empty())q.pop();

    memset(dist,0x7f,sizeof(dist));

    int i,v,temp;

    dist[0][S]=0;

    in[0][S]=1;

    q.push(Lux(0,S));

    while(!q.empty())

    {

        Lux U=q.front();q.pop();in[U.x][U.y]=0;

        for(i=head[U.y];i;i=e[i].next)

        {

            v=e[i].v;

            temp=U.x+red[v];

            if(temp<=lig&&dist[U.x][U.y]+e[i].len+ave[v]<=gas&&dist[temp][v]>dist[U.x][U.y]+e[i].len+ave[v])

            {

                dist[temp][v]=dist[U.x][U.y]+e[i].len+ave[v];

                if(!in[temp][v])in[temp][v]=1,q.push(Lux(temp,v));

            }

        }

    }

}

double divspfa(int S,int T)

{

    while(!q.empty())q.pop();

    memset(dist,0x7f,sizeof(dist));

    int i,j,v,temp;

    dist[0][S]=0;

    in[0][S]=1;

    q.push(Lux(0,S));

    while(!q.empty())

    {

        Lux U=q.front();q.pop();in[U.x][U.y]=0;

        for(j=0;j+U.x<=lig;j++)

        {

            for(i=HEAD[j][U.y];i;i=E[j][i].next)

            {

                v=E[j][i].v;

                if(dist[j+U.x][v]>dist[U.x][U.y]+E[j][i].len+cost)

                {

                    dist[j+U.x][v]=dist[U.x][U.y]+E[j][i].len+cost;

                    if(!in[j+U.x][v])in[j+U.x][v]=1,q.push(Lux(j+U.x,v));

                }

            }

        }

    }

    double ret=99999999999.999;

    for(i=0;i<=lig;i++)ret=min(ret,dist[i][T]);

    return ret;

}

void work()

{

    int i,j,k;

    double a,b,c;

    int ia,ib;

    int s,t,v;

    /*i just think it's not

        [graceful]

    to input in the main function. */

    scanf("%d%d%d%d%d",&n,&m,&lig,&gas,&cost);

    for(i=1;i<=n;i++)

    {

        trie.insert();

        if(k=trie.judge())

        {

            sta[i]=++num;

            gas_station[num]=i;

            if(k==1)s=i;

            if(k==3)t=i;

        }

        scanf("%lf%lf",&a,&b);

        if(k==1||k==3)continue;

        if(a>eps)

            red[i]=1,ave[i]=a*a/2.0/(a+b);

    }

    for(i=1;i<=m;i++)

    {

        ia=trie.insert();

        ib=trie.insert();

        scanf("%s",ttt);

        scanf("%lf",&c);

        add(ia,ib,c);

        add(ib,ia,c);

    }

    for(i=1;i<=num;i++)

    {

        prespfa(gas_station[i]);

        for(j=1;j<=num;j++)

        {

            v=gas_station[j];

            if(j!=i)

            {

                for(k=0;k<=lig;k++)

                {

                    if(dist[k][v]<inf)

                    {

                        ADD(k,i,j,dist[k][v]);

                    }

                }

            }

        }

    }

    printf("%.3lf\n",divspfa(sta[s],sta[t])-cost);

}

int main()

{

//  freopen("pathplan.in","r",stdin);

//  freopen("pathplan.out","w",stdout);

//  freopen("test.in","r",stdin);

    work();

    return 0;

}