题解 P1266 【速度限制】

· · 题解

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;
}

最后温馨提示:

-完结撒花