bzoj3245

bzoj3245

​​ 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

不是很想写dijkstra毕竟要写两个pair还有priority_queue

一到晚上，颈椎不舒服的时候，躺床上就容易不小心睡着，刚刚就是不小心又睡着了 怎么评价这题呢，和jloi还有usaco的那些题都非常像，也是相当于dp的思想吧（跪求自己记住这种思路x）

参照了下popoqqq如何给double memset赋值x（顺便看了金牌爷的经历）瞬间%%

#include#include#includeusing namespace std;#define pa pair#define N 155inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,next,v,len;}data[N*N];queue q;pa from[N][550];bool flag[N][550];double f[N][550];int h[N],n,m,d,num;void spfa(){ q.push(make_pair(0,70));flag[0][70]=true; memset(f,0x42,sizeof(f));f[0][70]=0; while (!q.empty()){ int x=q.front().first,vx=q.front().second;q.pop();flag[x][vx]=false; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,v=data[i].v,len=data[i].len; if (v){ if (f[x][vx]+(double)len/v

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。