分层图求最短路
速度限制
题目描述
在这个繁忙的社会中,我们往往不再去选择最短的道路,而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是,有一些限速的标志丢失了,因此你无法得知应该开多快。一种可以辩解的解决方案是,按照原来的速度行驶。你的任务是计算两地间的最快路线。
你将获得一份现代化城市的道路交通信息。为了使问题简化,地图只包括路口和道路。每条道路是有向的,只连接了两条道路,并且最多只有一块限速标志,位于路的起点。两地 $A$ 和 $B$,最多只有一条道路从 $A$ 连接到 $B$。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然,你的车速不能超过当前的速度限制。
输入格式
第一行是 $3$ 个整数 $N$,$M$ 和 $D$($2\leq N\leq 150$,$1\leq M\leq 22500$),表示道路的数目,用 $0 \sim N-1$ 标记。$M$ 是道路的总数,$D$ 表示你的目的地。
接下来的 $M$ 行,每行描述一条道路,每行有 $4$ 个整数 $A$($0\leq A<N$),$B$($0\leq B<N$),$V$ ($0\leq V\leq 500$)和 $L$($1\leq L\leq 500$),这条路是从 $A$ 到 $B$ 的,速度限制是 $V$,长度为 $L$。如果 $V$ 是 $0$,表示这条路的限速未知。
如果 $V$ 不为 $0$,则经过该路的时间 $T=\frac{L}{V}$。否则 $T=\frac{L}{\text{Vold}}$,$\text{Vold}$ 是你到达该路口前的速度。开始时你位于 $0$ 点,并且速度为 $70$。
输出格式
输出文件仅一行整数,表示从 $0$ 到 $D$ 经过的城市。
输出的顺序必须按照你经过这些城市的顺序,以 $0$ 开始,以 $D$ 结束。仅有一条最快路线。
样例 #1
样例输入 #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。vis[i][j]$表示从出发点到$i$,速度为$j$是否访问过。
为得到最短的路线,可以建一个$from[i][j]$数组,表示从出发点到$i$,速度为$j$的最短路的上一个点。最后跑一遍堆优化的$dijkstra$即可。
#include<bits/stdc++.h>
using namespace std;
const int N=160,M=510;
struct Node{
int to,v;
double l;
Node(int to=0,int v=0,double l=0):to(to),v(v),l(l) {}
};
int n,m,t;
double dis[N][M];
pair<int,int> lst[N][M];
int vis[N][M];
vector<Node> g[N];
vector<int> ans;
void bfs(){ //dijkstra
for(int i=1;i<=n;i++){
for(int j=1;j<=M;j++) dis[i][j]=2e9;
}
dis[1][70]=0;
priority_queue<pair<double,pair<int,int> > > pq;
pq.emplace(0,make_pair(1,70));
while(!pq.empty()){
int u=pq.top().second.first;
int o=pq.top().second.second;
pq.pop();
if(vis[u][o]) continue;
vis[u][o]=1;
for(auto v:g[u]){
if(v.v&&dis[v.to][v.v]>dis[u][o]+v.l/v.v){ //有速度限制
dis[v.to][v.v]=dis[u][o]+v.l/v.v;
lst[v.to][v.v]=make_pair(u,o);
pq.emplace(make_pair(-dis[v.to][v.v],make_pair(v.to,v.v)));
}
if(!v.v&&dis[v.to][o]>dis[u][o]+v.l/o){ //无速度限制
dis[v.to][o]=dis[u][o]+v.l/o;
lst[v.to][o]=make_pair(u,o);
pq.emplace(make_pair(-dis[v.to][o],make_pair(v.to,o)));
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&t);
t++;
for(int i=1;i<=m;i++){
int u,v,l,d;
scanf("%d%d%d%d",&u,&v,&l,&d);
u++;v++;
g[u].emplace_back(v,l,d);
}
bfs();
pair<int,int> now;
double maxn=2e9;
for(int i=1;i<M;i++){
if(dis[t][i]<maxn){
maxn=dis[t][i];
now=make_pair(t,i);
}
}
while(now.first){
ans.push_back(now.first-1);
now=lst[now.first][now.second];
}
reverse(ans.begin(),ans.end());
// reverse(ans.begin(),ans.back());
for(auto v:ans) printf("%d ",v);
return 0;
}
标签:pq,int,短路,leq,分层,pair,图求,make,dis
From: https://www.cnblogs.com/imfbustxhf/p/18526082