速度限制
题目描述
在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。
你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地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 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
输出样例#1： 复制
0 5 2 3 1
<br>
<font color="00ccff">题解</font>
不同于飞行路线的k次免费的分层图。 这一道实际上要更难一些？？（当然有些人会觉得这道更明显一些） 我们对速度进行分层。对于每一个点，考虑每一种到达它的速度情况，因为这样到达下一段路时你并不知道哪一个速度是更优的。 开二维，记录一下点和时间然后强行跑就可以了。
<br>
<font color="00ccff">代码</font>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
const int N=801;
int vis[N][N];
double dis[N][N];
int num=0,head[N];
struct node{
int to,v,lim,nex;
}e[N*N<<1];
struct nod{
int a,b;
}pre[N][N];
int n,m,t,ans;
double sum=99999999;
queue<pair<int,int> >q;
int read(){
int x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
void add(int from,int to,int v,int lim){
num++;
e[num].to=to;
e[num].v=v;
e[num].lim=lim;
e[num].nex=head[from];
head[from]=num;
}
void spfa(){
for(int i=0;i<=150;i++)for(int j=0;j<=500;j++)dis[i][j]=99999999;
dis[1][70]=0;vis[1][70]=1;
q.push(make_pair(1,70));
while(!q.empty()){
int u=q.front().first,vi=q.front().second;q.pop();vis[u][vi]=0;
// cout<<u<<' '<<vi<<endl;
for(int i=head[u];i;i=e[i].nex){
int v=e[i].to;
if(!e[i].lim){
if(dis[v][vi]>dis[u][vi]+1.0*e[i].v/vi)
{
dis[v][vi]=dis[u][vi]+1.0*e[i].v/vi;
pre[v][vi].a=u;
pre[v][vi].b=vi;
if(!vis[v][vi]){
vis[v][vi]=1;
q.push(make_pair(v,vi));
}
}
}
if(e[i].lim){
if(dis[v][e[i].lim]>dis[u][vi]+1.0*e[i].v/e[i].lim){
dis[v][e[i].lim]=dis[u][vi]+1.0*e[i].v/e[i].lim;
pre[v][e[i].lim].a=u;
pre[v][e[i].lim].b=vi;
if(!vis[v][e[i].lim]){
vis[v][e[i].lim]=1;
q.push(make_pair(v,e[i].lim));
}
}
}
}
}
}
void write(int x,int vi){
if(x!=1)write(pre[x][vi].a,pre[x][vi].b);
printf("%d ",x-1);
}
int main(){
n=read();m=read();t=read()+1;
for(int i=1;i<=m;i++){
int a=read()+1,b=read()+1,c=read(),d=read();
add(a,b,d,c);
}
spfa();
for(int i=0;i<=500;i++){
if(sum>dis[t][i])
{
sum=dis[t][i];
ans=i;
}
}
//cout<<ans<<endl;
write(pre[t][ans].a,pre[t][ans].b);
printf("%d",t-1);
return 0;
}