P1266 速度限制

题目描述

在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地A和B，最多只有一条道路从A连接到B。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。

输入输出格式

输入格式：

 

第一行是3个整数N，M和D(2<＝N<=150)，表示道路的数目，用0..N-1标记。M是道路的总数，D表示你的目的地。

接下来的M行，每行描述一条道路，每行有4个整数A(0≤A<N)，B(0≤B<N)，V(0≤V≤500)and L(1≤L≤500)，这条路是从A到B的，速度限制是V，长度为L。如果V是0，表示这条路的限速未知。

如果V不为0，则经过该路的时间T=L/V。否则T=L/Vold，Vold是你到达该路口前的速度。开始时你位于0点，并且速度为70。

 

输出格式：

 

输出文件仅一行整数，表示从0到D经过的城市。

输出的顺序必须按照你经过这些城市的顺序，以0开始，以D结束。仅有一条最快路线。

 

输入输出样例

输入样例#1： 

6 15 10 1 25 680 2 30 500 5 0 1011 2 70 771 3 35 422 0 0 222 1 40 862 3 0 232 4 45 403 1 64 143 5 0 234 1 95 85 1 0 845 2 90 645 3 36 40

输出样例#1： 

0 5 2 3 1

/*分层图最短路dis[i][j] 到i速度为j数组开大！！！！！！！！！！ */#include
       
        #define N 5007using namespace std;int head[N],size;int n,m,d,vis[N][N];double dis[N][N];struct edge{    int v,to,next;double w;}e[100007];struct node{
     int u,v;};node pre[N][N];void add(int x,int y,int v,double w){    e[++size].to=y;    e[size].next=head[x];    head[x]=size;    e[size].w=w;e[size].v=v;}void spfa(){     queue
        
         q;     q.push((node){
      0,70});     dis[0][70]=0;vis[0][70]=1;     while(q.empty()!=1)     {            node x=q.front();q.pop();             int u=x.u,sp=x.v;vis[u][sp]=0;            for(int i=head[u];i;i=e[i].next)            {                int tp=0,v=e[i].to;                tp=(e[i].v?e[i].v:sp);                if(tp)                if(dis[v][tp]>dis[u][sp]+(e[i].w*1.0/tp*1.0))                {                    pre[v][tp]=x;                    dis[v][tp]=dis[u][sp]+(e[i].w*1.0/tp*1.0);                    if(!vis[v][tp])                    {                        q.push((node){v,tp});                        vis[v][tp]=1;                    }                }            }      }}void print(int x,int speed){    if(x!=0)    print(pre[x][speed].u,pre[x][speed].v);    cout<
         
          <<' '; return;}int main(){    scanf("%d%d%d",&n,&m,&d);    for(int i=1;i<=n;i++)    for(int j=0;j<=500;j++)    dis[i][j]=19260817;    for(int i=1;i<=m;i++)    {        int x,y,v; double w;        scanf("%d%d%d%lf",&x,&y,&v,&w);        add(x,y,v,w);    }    spfa();    double now=192608173;    int ans;    for(int i=1;i<=500;i++)    {        if(dis[d][i]