自动搬运

查看原文

来自洛谷，原作者为

	啧啧啧 这个人很懒，什么都没有留下.....

搬运于2025-08-24 21:23:07，当前版本为作者最后更新于2019-10-12 10:04:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P1266 速度限制题解

昨天考图论专题时考了这题(T4),当时一脸懵,暴力dijkstra还是boom 0.后来这位大佬教了我分层图. 于是我便穷困潦倒、千辛万苦、艰苦卓绝、含辛茹苦(轻松)地A了它

题解里只有一篇dijkstra的题解,所以我也来水一篇.

---

废话终结 进入正题

思路:

本题有限速与路程两个条件.而为了时间最短(速度最快),所以限速便是速度(读者自证不难),而为了时间最短,所以我们以t(=s/v)为权值来跑dijkstra.

但是仔细读题,会发现每一条边的长度固定,但是速度不一定只有一种.设一条边没有限速时,它的速度是可能不唯一的.而如果单纯把它的速度设为它的前一条:

void dj(){
	while(!p.empty()) p.pop();
	for(int i=1;i<=n;i++) dis[i]=1e9;
	p.push(make_pair(0,make_pair(1,70)));
	vis[1]=1;
	dis[1]=0;
	while(!p.empty()){
		int x=p.top().second.first;
		int batt=p.top().second.second;
		vis[x]=0;
		p.pop();
		for(int i=head[x];i;i=t[i].next){
			int y=t[i].to;
			if(t[i].bat){
				if((double)dis[y]>(double)dis[x]+(double)t[i].longg/(double)t[i].bat){
//					printf("from %d   to %d\	n",x,y);
					from[y]=x;
					dis[y]=(double)dis[x]+(double)t[i].longg/(double)t[i].bat;
					if(vis[y]) continue;
					vis[y]=1;
					p.push(make_pair(-dis[y],make_pair(y,t[i].bat)));
				}
				continue;
			}
			else{
				if((double)dis[y]>(double)dis[x]+(double)t[i].longg/(double)batt){
//					printf("from %d   to %d\n",x,y);
					from[y]=x;
					dis[y]=(double)dis[x]+(double)t[i].longg/(double)batt;
					if(vis[y]) continue;
					vis[y]=1;
					p.push(make_pair(-dis[y],make_pair(y,batt)));
				}
				continue;
			}
		}
	}
//	for(int i=1;i<=n;i++) printf("from[%d]=%d\n",i,from[i]);
//	for(int i=1;i<=n;i++) printf("dis[%d]=%lf\n",i,dis[i]);
	cout<<"0"<<" ";
	for(int i=d;i!=1;i=from[i]) printf("%d ",i);
	cout<<d-1<<endl;
}

那就是错的

(别急着抄)

所以我们引入正题:分层图(这个链接是假的)

大家应该都知道dijkstra的常规操作以及数组:

1 dis[i]:出发点到点i的距离 (本题中为时间)

2 vis[i]:第i个点是否在队列(我的解释可能不普及)

那么在分层图中,我们给它们做个升级:

dis[i][j]:出发点到点i,速度为j时(可以理解成j的前一个点到j的速度为j)的距离(时间)

vis[i][j]:同上

那么对于每一个点x扩展到点y时:

- 如果边(x,y)的速度为0,那么便有:

if(...)
	dis[y][old_v]=dis[x][old_v]+(x,y).s/old_v;

//old_v为上一条的限速(代码中为vs)

//(x,y)为连接x与y的边

- 如果边(x,y)有速度,那么便有:

if(...)
	dis[y][now_v]=dis[x][old_v]+(x,y).s/now_v;

//old_v为上一条的限速

//now_v为现在的限速

//(x,y)为连接x与y的边

(清晰易懂)

好的呢,那就这样了吧.

输出存路径需要一个:

from[i][j]:点i(速度为j)的前一个点为from[i][j];

最后再一个递归就ok辽呢.

上代码

#include<bits/stdc++.h>
using namespace std;
int n,m,d;//点 边 终点
int tot,head[10001];
int vis[1001][1001];//如题解 
double dis[1001][1001];//如题解 
struct Node{
	int to,v,s;//点 限速 路程
	int next; 
}t[100001]; 
struct Nodee{
	int x,v;
}from[1001][1001];
void add(int from,int to,int v,int s){
	tot++;
	t[tot].to=to;
	t[tot].v=v;
	t[tot].s=s;
	t[tot].next=head[from];
	head[from]=tot;
}
void out(int x,int v){//输出递归 x为点 v为速度(别把v当做点) 
	if(x==1) return;
	out(from[x][v].x,from[x][v].v);
	printf("%d ",x-1);//在输入时+1了 
}
void dj(){
	priority_queue<pair<double,pair<int,int> > >p;//时间,点,速度 
	p.push(make_pair(0,make_pair(1,70)));
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=1000;j++){
			dis[i][j]=1e9+1;
		}
	} 
	dis[1][70]=0;
	vis[1][70]=1;
	while(!p.empty()){
		int x=p.top().second.first;
		int vs=p.top().second.second;
		vis[x][vs]=0;
		p.pop();
		for(int i=head[x];i;i=t[i].next){//如题解 
			int y=t[i].to;
			int n_v=t[i].v;
			if(t[i].v){//有速度 
				if(dis[y][n_v]>dis[x][vs]+(double)t[i].s/(double)n_v){
					dis[y][n_v]=dis[x][vs]+(double)t[i].s/(double)n_v;
//					printf("from %d  to %d\n",x-1,y-1);
					from[y][n_v]={x,vs};
					if(vis[y][n_v]) continue;
					vis[y][n_v]=1;
					p.push(make_pair(-dis[y][n_v],make_pair(y,n_v)));
				
				}
				continue;
			}
			if(!t[i].v){//无速度 
				n_v=vs;//照原来速度跑
				if(dis[y][n_v]>dis[x][vs]+(double)t[i].s/(double)n_v){
					dis[y][n_v]=dis[x][vs]+(double)t[i].s/(double)n_v;
//					printf("from %d  to %d\n",x-1,y-1);	
					from[y][n_v]={x,vs};
					if(vis[y][n_v]) continue;
					vis[y][n_v]=1;
					p.push(make_pair(-dis[y][n_v],make_pair(y,n_v)));
				} 
				continue;
			}
		}
	}
	int min_=0;
	dis[d][min_]=1e9+100;
	for(int i=1;i<=1000;i++){
		if(dis[d][min_]>=dis[d][i]&&dis[d][i]!=1e9+1) min_=i;
	}
//	printf("%lf\n",dis[d][min_]);
	printf("0 ");
	out(d,min_);
	printf("\n");
}

int read(){
	int f1=0,f2=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f2=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		f1=(f1<<1)+(f1<<3)+(ch^48);
		ch=getchar();
	}
	return f1*f2;
}
int main(){
	n=read(),m=read(),d=read();
	d++;
	for(int i=1;i<=m;i++){
		int A=read(),S=read(),D=read(),F=read();
		A++,S++;
		add(A,S,D,F);
//		add(S,A,D,F);	
	}
	dj();
	return 0;
}

最后温馨提示:

• m至少为 100001

• 点建议在输入时+1(最后输出记得-1)

-完结撒花

• 代码都抄了,赞是不是也要点?

• 可以加我滴QQ(3147280295)不懂问我丫(抄代码也要理解哦)