【学习笔记】CF576D Flights for Regular Customers

这篇具有很好参考价值的文章主要介绍了【学习笔记】CF576D Flights for Regular Customers。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

不同于传统的最短路，当我们走到一个节点的时候，还要记录此时经过的边数才能完成转移。但是第二维太大了，太抽象了！

看到 $m$ 这么小，很难不想到离散化。那么设 $f_{i,j}$ 表示当第 $i$ 条边出现时，在节点 $j$ 是否可行，注意这是 $01$ 状态。转移非常粗暴，因为我们要在当前的边集下逗留 $d_{i+1}-d_i$ 步，所以直接每次跳 $2^i$ 步即可。

算一下复杂度，居然是 $n^3m\log V$ ，因为每加入一条边都要跑一遍 $\text{Floyd}$ ，太抽象了！！因为是 $01$ 状态所以可以用 $\text{bitset}$ 优化，这样复杂度 $\frac{n^3}{w}m\log V$ ，这样算下来已经可以通过了。。。

发现问题瓶颈在于计算邻接矩阵的 $k$ 次幂上面，可以采取动态加边的思想来维护，然后因为左乘的是一个向量（哪些点可达），所以这一部分也可以少一个 $n$ 。这样复杂度 $\frac{n^2}{w}m\log V$ 。但是为什么没有人写这个做法呢？文章来源地址https://www.toymoban.com/news/detail-531199.html

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=155;
int n,m,res=0x3f3f3f3f,dis[N];
queue<int>Q;
struct node{
    bitset<N>f[N];
    node(){for(int i=1;i<=n;i++)f[i].reset();}
    node operator *(const node &a)const{
        node r;
        for(int i=1;i<=n;i++)assert(r.f[i].count()==0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(f[i][j]){
                    r.f[i]|=a.f[j];
                }
            }
        }
        return r;
    }
}f,mat;
struct edge{
    int x,y,d;
    bool operator <(const edge &a)const{
        return d<a.d;
    }
}edges[N];
bitset<N>arrays;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;for(int i=1;i<=m;i++)cin>>edges[i].x>>edges[i].y>>edges[i].d;
    sort(edges+1,edges+1+m);
    arrays[1]=1;
    for(int i=1;i<=m;i++){
        int x=edges[i].x,y=edges[i].y,k=edges[i].d-edges[i-1].d;
        f=mat;
        for(;k;k>>=1){
            if(k&1){
                bitset<N>tmp;
                for(int j=1;j<=n;j++){
                    for(int k=1;k<=n;k++){
                        if(f.f[j][k]&&arrays[j])tmp[k]=1;
                    }
                }
                arrays=tmp;
            }
            f=f*f;
        }
        mat.f[x][y]=1;
        memset(dis,0x3f,sizeof dis);
        for(int j=1;j<=n;j++){
            if(arrays[j]){
                Q.push(j),dis[j]=edges[i].d;
            }
        }
        while(Q.size()){
            int u=Q.front();Q.pop();
            for(int v=1;v<=n;v++){
                if(mat.f[u][v]&&dis[u]+1<dis[v]){
                    dis[v]=dis[u]+1;
                    Q.push(v);
                }
            }
        }
        res=min(res,dis[n]);
    }
    if(res==0x3f3f3f3f)cout<<"Impossible";
    else cout<<res;
}