【bzoj3245】【最快路线】【spfa】-白红宇的个人博客

发布日期：2021-11-16 15:38:52 浏览次数：1 分类：技术文章

本文共 2199 字，大约阅读时间需要 7 分钟。

Description

精明的小R每每开车出行总是喜欢走最快路线,而不是最短路线.很明显,每条道路的限速是小R需要考虑的关键问题.不过有一些限速标志丢失了,于是小R将不知道能开多快.不过有一个合理的方法是进入这段道路时不改变速度行驶.你的任务就是计算从小R家(0号路口)到D号路口的最快路线.

现在你得到了这个城市的地图,这个地图上的路都是单向的,而且对于两个路口A和B,最多只有一条道路从A到B.并且假设可以瞬间完成路口的转弯和加速.

Input

第一行是三个整数N,M,D(路口数目,道路数目,和目的地). 路口由0...N-1标号

接下来M行，每行描述一条道路:有四个整数A,B,V,L,(起始路口,到达路口,限速,长度) 如果V=0说明这段路的限速标志丢失.

开始时你位于0号路口,速度为70.

Output

仅仅一行,按顺序输出从0到D经过的城市.保证最快路线只有一条.

Sample Input

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

Sample Output

0 5 2 3 1

HINT

【数据范围】

30% N<=20

100% 2<=N<=150;0<=V<=500;1<=L<=500

题解：

记录一下到点x的速度。

spfa的时候分有限速和没限速讨论一下即可。

可以看成是拆点spfa.

代码：

#include
    
     #include
     
      #include
      
       #define N 200#define M 40000#define inf 2100000000using namespace std;int n,m,T,cnt,x,y,v,l,f[N][510],a[N],next[M<<1],point[N];double dis[N][510],ans;pair
       
        q[N*500*10],pre[N][510];struct use{int st,en,v,l;}e[M<<1];void add(int x,int y,int v,int l){   next[++cnt]=point[x];point[x]=cnt;   e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;e[cnt].l=l;}void spfa(){  int h(0),t(1);  for (int i=1;i<=n;i++)   for (int j=0;j<=500;j++)      dis[i][j]=inf;  dis[1][70]=0;q[t]=make_pair(1,70);   while(h
        
         dis[x][y]+(double)e[i].l/(double)e[i].v){      	  dis[e[i].en][e[i].v]=dis[x][y]+(double)e[i].l/(double)e[i].v;      	  pre[e[i].en][e[i].v]=make_pair(x,y);      	  if (!f[e[i].en][e[i].v]){      	    q[++t]=make_pair(e[i].en,e[i].v);      	    f[e[i].en][e[i].v]=1;          }        }      }      else{      	if (dis[e[i].en][y]>dis[x][y]+(double)e[i].l/(double)y){          dis[e[i].en][y]=dis[x][y]+(double)e[i].l/(double)y;		  pre[e[i].en][y]=make_pair(x,y);		  if (!f[e[i].en][y]){		    q[++t]=make_pair(e[i].en,y);		    f[e[i].en][y]=1;		  }         }      }     }   }}void out(int x,int y){   if (x!=1) out(pre[x][y].first,pre[x][y].second);   printf("%d",x-1);   if (x!=T) printf(" ");}int main(){  scanf("%d%d%d",&n,&m,&T);T++;  for (int i=1;i<=m;i++){    scanf("%d%d%d%d",&x,&y,&v,&l);    x++;y++;add(x,y,v,l);  }	  spfa();ans=inf;  for (int i=1;i<=500;i++)    if (dis[T][i]<=ans){       ans=dis[T][i];x=i;    }  out(T,x);}

转载地址：https://blog.csdn.net/sunshinezff/article/details/51145395 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj3373】【说谎的牲畜】【差分约束】

下一篇：【bzoj1726】【Usaco2006 Nov】【Roadblocks第二短路】【spfa】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！