P1266 速度限制(分层图spfa)
2024-09-30 20:34:33
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 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
/*
分层图最短路
dis[i][j] 到i速度为j
数组开大!!!!!!!!!!
*/
#include<bits/stdc++.h> #define N 5007 using 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[];
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<node>q;
q.push((node){,});
dis[][]=;vis[][]=;
while(q.empty()!=)
{
node x=q.front();q.pop();
int u=x.u,sp=x.v;vis[u][sp]=;
for(int i=head[u];i;i=e[i].next)
{
int tp=,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]=;
}
}
}
}
} void print(int x,int speed)
{
if(x!=)
print(pre[x][speed].u,pre[x][speed].v);
cout<<x<<' '; return;
} int main()
{
scanf("%d%d%d",&n,&m,&d);
for(int i=;i<=n;i++)
for(int j=;j<=;j++)
dis[i][j]=;
for(int i=;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=;
int ans;
for(int i=;i<=;i++)
{
if(dis[d][i]<now)
now=dis[d][i],ans=i;
}
print(d,ans);
return ;
}
最新文章
- curl的登录总结
- C++ - 静态成员函数
- STM32的寄存器控制SDA_IN()/SDA_OUT()
- exynos 4412 电源管理芯片PMIC 的配置及使用方法
- window.history
- 对同一个项目下的多个数据库Context进行迁移Migrations
- Finding Palindromes - 猥琐的字符串(Manacher+trie)
- js中的eval方法转换对象时,为何一定要加上括号?
- Swiper.js
- Lustre文件系统测试——obdfilter-survey测试
- Acer Aspire E1 471G 加装SSD+机械盘后无法启动的问题
- 使用Intent传递对象
- [AtCoder 2702]Fountain Walk - LIS
- JQuery小知识
- websocket session共享
- react用class关键字来创建组件
- IT设备服务监控的方法论
- 修改tomcat启动窗口的名称
- noip第29课作业
- Inno Setup 软件封装