AcWing 920. 最优乘车--优化

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 920. 最优乘车--优化原题链接中等

作者：

lixiaoqian_qwq , 2020-07-16 22:28:23 , 所有人可见 , 阅读 5527

22

5

这里讨论的是最优乘车的优化！
标答请移步至此

--------------------------------以下是原回答--------------------------------------

优化在于建图方式

标答中，每一条公交线路都要建 $n(n-1)/2$ 条边
为了提升效率，我们需要减少边数

方法

利用yxc的”虚拟源点”思想，可以给每条公交线路一个专用的虚拟源点。

把每条公交线路分成相等的2块，前一块所有点与虚拟源点连边，后一块所有点与虚拟源点连边。

利用分治思想，前后2块内部各自再创建虚拟源点。

时间复杂度 $O(mnlogn)$

代码如下：

// 感谢 @Shen666 指出的用getchar优化代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std ;
const int N=1010 ;
int m,n ;
int h[N],e[N*2],ne[N*2],w[N*2],idx ;
int dis[N] ;
int stop[N] ;
int add_cnt ;
void add(int a,int b,int c)
{
    e[idx]=b ;
    w[idx]=c ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
void Add(int stop[],int start,int end)
{
    add_cnt++ ;
    if(start>=end) return ;
    for(int i=start;i<=(start+end>>1);i++) add(stop[i],add_cnt,0) ;
    for(int i=(start+end>>1)+1;i<=end;i++) add(add_cnt,stop[i],1) ;
    Add(stop,start,start+end>>1) ;
    Add(stop,(start+end>>1)+1,end) ;
}
void bfs()  //和SPFA一个样子
{
    queue<int> q ;
    q.push(1) ;
    memset(dis,0x3f,sizeof dis) ;
    dis[1]=0 ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i] ;
                q.push(j) ;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&m,&n),getchar() ;
    add_cnt=n ;
    string str ;
    memset(h,-1,sizeof h) ;
    while(m--)
    {
        int cnt=0 ;
        string str ;
        getline(cin,str) ;
        memset(stop,0,sizeof stop) ;
        for(auto ch:str)
        {
            if(ch==' ') cnt++ ;
            else stop[cnt]=stop[cnt]*10+ch-'0' ;
        }
        Add(stop,0,cnt) ;
    }
    bfs() ;
    if(dis[n]>1e9) puts("NO") ;
    else printf("%d",dis[n]-1) ;
    return 0 ;
}

20ms优化至18ms!

22 评论

szh_2003 2023-01-10 16:56

用getchar()把一开始的回车处理掉，就不用单独处理了。

lixiaoqian_qwq 2023-01-11 00:43

有道理诶！

Aaron_wch 2022-08-31 10:02

优化至11毫秒，还有更快的吗

#include <cstdio>
using namespace std;
const int N=510;
int elast[N],idx=1;
struct path{
    int y,next;
}a[N*N];
void add(int x,int y){
    a[idx]=(path){y,elast[x]};
    elast[x]=idx++;
}
int map[N][N];
int q[N],hh,tt=-1;
int read(int &x){
    x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='\n')return 0;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(ch=='\n')return -1;
    return 1;
}
int m,n;
int d,tp[N];
int dis[N];
int vis[N];
int x,y;
int main(){
    scanf("%d%d\n",&m,&n);
    while(m--){
        d=0;
        while(1){
            y=read(x);
            if(y==-1){
                tp[d++]=x;
                break;
            }
            if(y==1)tp[d++]=x;
            else{
                break;
            }
        }
        for(int i=0;i<d;i++){
            for(int j=i+1;j<d;j++){
                if(!map[tp[i]][tp[j]]){
                    map[tp[i]][tp[j]]=1;
                    add(tp[i],tp[j]);
                }
            }
        }
    }
    q[++tt]=1;
    vis[1]=1,dis[1]=-1;
    while(hh<=tt){
        x=q[hh++];
        for(int i=elast[x];i;i=a[i].next){
            y=a[i].y;
            if(vis[y]==0){
                dis[y]=dis[x]+1;
                vis[y]=1;
                if(y==n){
                    printf("%d\n",dis[y]);
                    return 0;
                }
                q[++tt]=y;
            }
        }
    }
    puts("NO");
    return 0;
}

作者：Aaron_wch
链接：https://www.acwing.com/solution/content/135602/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

lixiaoqian_qwq 2022-08-31 14:31

%%%

jatro13 2022-11-19 22:13

orz

Sma10 2023-02-22 15:24 回复了 lixiaoqian_qwq 的评论

%%%%

Bigwave 2022-06-20 17:59

#### 优化至13ms

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define R register
#define PII pair<int, int>

const int N = 510, M = 110;
int n, m, temp[N];
bool st[N];
int h[N], e[N * M], ne[N * M], idx;

void add(int a, int b)
{
    e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void solve()
{
    cin >> m >> n;
    string line;
    getline(cin, line);
    for (R int i = 1; i <= m; ++ i)
    {
        getline(cin, line);
        stringstream ssin(line);
        int stop, cnt = 0;
        while (ssin >> stop) temp[cnt ++] = stop;
        for (R int i = 0; i < cnt; ++ i)
            for (R int j = i + 1; j < cnt; ++ j)
                add(temp[i], temp[j]);
    }

    queue<PII> q;
    q.push({0, 1});
    st[1] = true;

    while (q.size())
    {
        auto [d, t] = q.front(); q.pop();
        st[t] = true;
        if (t == n)
        {
            cout << d - 1 << endl;
            return;
        }

        for (int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
                q.push({d + 1, j});
        }
    }
    puts("NO");
}

int main()
{
    ios; solve();
}

Bigwave 2022-06-20 17:53

#### 优化至15ms

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define R register
#define PII pair<int, int>

const int N = 510, M = 110;
int n, m, temp[N];
bool st[N], g[N][N];


void solve()
{
    cin >> m >> n;
    string line;
    getline(cin, line);
    for (R int i = 1; i <= m; ++ i)
    {
        getline(cin, line);
        stringstream ssin(line);
        int stop, cnt = 0;
        while (ssin >> stop) temp[cnt ++] = stop;
        for (R int i = 0; i < cnt; ++ i)
            for (R int j = i + 1; j < cnt; ++ j)
                g[temp[i]][temp[j]] = true;
    }

    queue<PII> q;
    q.push({0, 1});
    st[1] = true;

    while (q.size())
    {
        auto [d, t] = q.front(); q.pop();
        st[t] = true;
        if (t == n)
        {
            cout << d - 1 << endl;
            return;
        }

        for (R int j = 1; j <= n; ++ j)
        {
            if (!st[j] && g[t][j])
            {
                q.push({d + 1, j});
            }
        }
    }
    puts("NO");
}

int main()
{
    ios; solve();
}

lixiaoqian_qwq 2022-06-24 19:48

好先进的语法！值得鼓励！

LSC_lsc 2022-05-29 13:03

dfs版本的建图方式是有问题的
4 15
11 2
1 3 4 5 9
3 6 11
2 7 8 10 11 12 13 15
这个样例就过不去，答案是2，dfs版本跑出来的是3

lixiaoqian_qwq 2022-06-04 16:08

似乎也是诶遇到环就处理不了。。。

LSC_lsc 2022-06-04 16:50 回复了 lixiaoqian_qwq 的评论

已经提交工单了，再交应该就过不去了…

lixiaoqian_qwq 2022-06-07 15:13 回复了 LSC_lsc 的评论

确实当时我大意了提醒一下大家只有在DAG里面才可以用dfs！碰到环就不可以dfs了！

晒干了沉默 2022-05-04 09:38

我有一个想法单是我太菜了我不敢说出来

lixiaoqian_qwq 2022-05-04 17:00

说出来！

晒干了沉默 2022-05-09 07:55 回复了 lixiaoqian_qwq 的评论

那个dfs的时间复杂度应该是nlogn，优化了不少，不是传统意义上的dfs爆搜。属于两个或者多个方向同时进行。类似于分治。dfs爆搜应该是直接进行搜索，把每一条通向N的路求出来，然后取一个最小值。这个时间复杂度就高了，其实作者的第一个方法和第二个方法是一样的复杂度

lixiaoqian_qwq 2022-05-09 20:50 回复了晒干了沉默的评论

好的！

lixiaoqian_qwq 2022-05-09 20:50 回复了晒干了沉默的评论

感谢支持

夜林 2022-02-03 20:17

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
const int N = 510;
int q[N * N];
bool g[N][N];
int dist[N];
int stop[N];
int n,m;

int bfs(){
    memset(dist,0x3f,sizeof dist);
    int hh = 0,tt = 0;
    q[0] = 1;
    dist[1] = 0;
    while(hh <= tt){
        int t = q[hh ++];

        for(int i = 1; i <= n; ++ i){
            if(g[t][i] && dist[i] == 0x3f3f3f3f){
                dist[i] = dist[t] + 1;
                q[++ tt] = i;
            }
        }
    }
    return dist[n];
}

int main()
{
    cin >> m >> n;
    string line;
    getline(cin,line);//吞掉上一行回车
    while(m -- ){

        getline(cin,line);
        stringstream ss(line);
        int cnt = 0,p;
        while(ss >> p)stop[cnt ++] = p;
        for(int i = 0; i < cnt ; ++ i){
            for(int j = i + 1; j < cnt; ++ j){
                g[stop[i]][stop[j]] = true;
            }
        }
    }
    bfs();
    if(dist[n] == 0x3f3f3f3f)puts("NO");
    else cout << max(dist[n] - 1,0) << endl;

    return 0;
}