「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
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
题解
用dis[i][j]表示到i点速度为的最短时间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,d,cnt; int head[151],fromn[151][501],fromv[151][501],q[75001],v[75001]; double dis[151][501]; bool inq[151][501]; struct data{int to,next,v,l;}e[50001]; void insert(int a,int b,int v,int l) { e[++cnt].to=b;e[cnt].v=v;e[cnt].l=l; e[cnt].next=head[a];head[a]=cnt; } void spfa() { int t=0,w=1,i,v0,now; memset(dis,127,sizeof(dis)); q[0]=0;v[0]=70; dis[0][70]=0; inq[0][70]=1; while(t!=w) { now=q[t];v0=v[t];t++;if(t==75001)t=0; i=head[now]; while(i) { if(!e[i].v&&(double)e[i].l/v0+dis[now][v0]<dis[e[i].to][v0]) { dis[e[i].to][v0]=(double)e[i].l/v0+dis[now][v0]; fromn[e[i].to][v0]=now; fromv[e[i].to][v0]=v0; if(!inq[e[i].to][v0]){ inq[e[i].to][v0]=1; q[w]=e[i].to; v[w]=v0; w++; if(w==75001)w=0;} } if(e[i].v&&(double)e[i].l/e[i].v+dis[now][v0]<dis[e[i].to][e[i].v]) { dis[e[i].to][e[i].v]=(double)e[i].l/e[i].v+dis[now][v0]; fromn[e[i].to][e[i].v]=now; fromv[e[i].to][e[i].v]=v0; if(!inq[e[i].to][e[i].v]){ inq[e[i].to][e[i].v]=1; q[w]=e[i].to; v[w]=e[i].v; w++; if(w==75001)w=0;} } i=e[i].next; } inq[now][v0]=0; } } void print(int x,int y) { if(x!=0)print(fromn[x][y],fromv[x][y]); printf("%d",x); if(x!=d)printf(" "); } int main() { scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=m;i++) { int a,b,v,l; scanf("%d%d%d%d",&a,&b,&v,&l); insert(a,b,v,l); } spfa(); int ans;double mn=0x7fffffff; for(int i=0;i<=500;i++) {if(dis[d][i]<mn){ans=i;mn=dis[d][i];}} print(d,ans); return 0; } |
Subscribe
计数器 9854434
OI 课件=>
OI 课件=>